【枚举+数学】CF1781D Many Perfect Squares

谁践踏了优雅 2024-03-22 15:30 15阅读 0赞

**n很小时，可以考虑双指针看看有没有什么性质**

[Many Perfect Squares - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][Many Perfect Squares - _ _ _ _luogu.com.cn]

题意：

![e0dbf188cf4f4d23bcd4c1d5b11d483a.png][]

思路：

n，1~50：对n暴力

x，0~1e18：O(1)计算

完全平方数：p^2

![ea33d57369364e4d8430964822b8d8a9.png][]

![86512fea96d343e5beb2ac8fbfe8cbeb.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int mod=998244353;
    
    int N,ans=1;
    int a[60];
    
    bool check(int x){
    	int t=sqrt(x);
    	return t*t==x;
    }
    void solve(){
    	ans=1;
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	//sort(a+1,a+1+N);
    	for(int i=1;i<=N;i++){
    		for(int j=i+1;j<=N;j++){
    			int u=a[j]-a[i];
    			for(int t=1;t*t<=u;t++){
    				if(u%t!=0||(u/t+t)%2==1) continue;
    				int tmp=(u/t-t)/2;
    				int x=tmp*tmp-a[i];
    				if(x<0) continue;
    				int cnt=0;
    				for(int l=1;l<=N;l++){
    					if(check(a[l]+x)) cnt++;
    				}
    				ans=max(ans,cnt);
    			}
    		}
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Many Perfect Squares - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/CF1781D#submit
[e0dbf188cf4f4d23bcd4c1d5b11d483a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/426415233abe4e6d86bace871f97f8e5.png
[ea33d57369364e4d8430964822b8d8a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/ad4a1c3c3fd2421f94495f0ba600ec84.png
[86512fea96d343e5beb2ac8fbfe8cbeb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/8a21f4c8274d4c29b04a1d360565dd37.png