CF1781 D. Many Perfect Squares [数学题]

传送门:CF

[前题提要]:一道有意思的数学题

直接想这道题是不好想的(博主当时就完全没有思路).那么考虑将一个大问题分解成一个小问题想一下(感觉这种思考方式在CF题中还是挺常见的),考虑如果同时存在多个完全平方数,那么必然满足存在两个完全平方数.而当我们确定了任意两个数之后,我们就可以反推出其他数.

考虑如果存在两个数同时为完全平方数会发生什么?
$$a[i]+x=p^2,a[j]+x=q^2$$$$a[j]-a[i]=q^2-p^2=(q+p)\ast (q-p)$$不难发现存在这样的一个事实,两个数的差一定可以分解为两个因子.诶,那么此时我们完全可以枚举差的因数,当我们枚举这个时,我们同时也就确定了$x$

那么此时这道题的解法也就呼之欲出了,我们先枚举任意两个数,将其作为我们假设的完全平方数,因为假设我们同时存在更多的完全平方数,这种情况必然是包括上述我们枚举的情况的.考虑确定完两个数之后,我们就可以通过枚举因数来确定$x$,确定完$x$之后,我们可以将其代回去,对于我们的每一个数都加上$x$,从而计算出此时的贡献,然后取一个$max$即可.

考虑$1e9$以内的最大因数个数很少,是$1e3$级别的(准确来说是1344个),所以此时我们的复杂度为$1e3\ast n^3+n^2\sqrt{n}$,差不多为$2e8$,4s时限能够接受.

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
   
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
inline void print(__int128 x){
   
	if(x<0) {
   putchar('-');x=-x;}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[maxn];
signed main() {
   
	int T=read();
	while(T--) {
   
		int n=read();
		for(int i=1;i<=n;i++) {
   
			a[i]=read();
		}
		int ans=1;
		for(int i=1;i<=n;i++) {
   
			for(int j=i+1;j<=n;j++) {
   
				vector<pair<int,int> >v; 
				int limit=__builtin_sqrt(a[j]-a[i]);
				for(int k=1;k<=limit;k++) {
   
					if((a[j]-a[i])%k==0) {
   
						int num1=min(k,(a[j]-a[i])/k);
						int num2=max(k,(a[j]-a[i])/k);
						v.push_back({
   num1,num2});
					}
				}
				for(auto [x,y]:v) {
   
					int q=(x+y)/2;int p=(y-x)/2;
					int X=q*q-a[j];
					if(!(X>=0&&X<=1e18)) continue;
					int sum=0;
					for(int k=1;k<=n;k++) {
   
						if((a[k]+X)==(int)__builtin_sqrt(a[k]+X)*(int)__builtin_sqrt(a[k]+X)) {
   
							sum++;
						}
					}
					ans=max(ans,sum);
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}