【枚举+数学】代码源每日一题div2 数学

清疚 2024-03-16 18:42 46阅读 0赞

[数学 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![d1eee51010a84b54a581fb5071c27e7d.png][]

思路：

首先把条件理一下

gcd(s1,s2)=K

按照惯用套路

设

s1=k1\*K

s2=k2\*K

那么就是(k1+k2)\*K=sum

所以K是sum的一个因子

因此只需要枚举sum的因子即可

但是注意数据范围：1e9

说明不能直接枚举，怎么办呢

注意到还有个条件我们没有利用：数列是1~N的

这意味着sum=(N+1)\*N/2

也就是说我们要枚举(N+1)\*N/2的因子，其实就是找出它的最大因子

那么只需要分开枚举即可，然后求一下最大值\*次大值 和 次大值\*最大值 的 最大值

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    using i64 = long long;
    
    const int mxn=1e5+10;
    
    int N,u,v;
    
    void solve(){
    	cin>>N;
    	if(N%2==1) u=N,v=(N+1)/2;
    	else u=N/2,v=N+1;
    	priority_queue<int> Q,Q2;
    	for(int i=1;i<=u/i;i++){
    		if(u%i==0){
    			Q.push(i);
    			if(i!=u/i) Q.push(u/i);
    		}
    	}
    	int mx1=Q.top();
    	Q.pop();
    	int mxx1=Q.top();
    	for(int i=1;i<=v/i;i++){
    		if(v%i==0){
    			Q2.push(i);
    			if(i!=v/i) Q2.push(v/i);
    		}
    	}
    	int mx2=Q2.top();
    	Q2.pop();
    	int mxx2=Q2.top();
    	cout<<max(mx1*mxx2,mxx1*mx2)<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/course/11/problem/47
[d1eee51010a84b54a581fb5071c27e7d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c07fe1dbfbe6420f94c04ad85c2d6828.png