D. Many Perfect Squares

题目链接：Problem - D - Codeforces 

题意：给你一个数组，大小不超过50个。

问你让他们全部加上一个x，构造出来最多能够有多少个完全平方数。

思路：

先对数组排个序，首先它最少一定是有一个的，然后判断数组中的两个数之间能不能求取确定一个x满足两个，然后再枚举每个数组加上这个x是不是完全平方数。求取最大结果就行了。

两个数求取x的过程为：

假设：a[i]+x=n*n       a[j]+x=m*m;

所以a[i]-a[j]=n*n-m*m =（n-m）*(n+m)  (这里我们排序后默认a[i]>a[j].

所以a[i]-a[j]=p*q;

n-m=p;  n+m=q;

n=(p+q)/2.   m=(q-p)/2.    

x=n*n-a[i].

关于p，其实p就是a[i]-a[j]的较小的因子部分。过程中需要判断p+q是否相加为偶数以及q-p是不是偶数，因为n和m需要为整数。然后还要判断x的范围为0<=x<=1e18.

然后对数组中每个数加上x，求取最多的ans就行了。 

AC代码：

#include<bits/stdc++.h>
#define lmw ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
const int N=1e6+10;
int a[N];
int check(int x){if((int)sqrt(x)*(int)sqrt(x)==x) return 1;else return 0;
}
void solve(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int ans=1;for(int i=1;i<=n;i++){for(int j=1;j<i;j++){int op=a[i]-a[j];for(int k=1;k<sqrt(op);k++){int num=0;if(op%k==0){int q=op/k;int p=k;if((p+q)%2==0&&(q-p)%2==0){int nn=(p+q)/2;int mm=(q-p)/2;int x=nn*nn-a[i];if(x>=0&&x<=1e18){for(int p=1;p<=n;p++){if(check(a[p]+x)){num++;}}							}}}ans=max(ans,num);}		}} cout<<ans<<"\\n";
}
signed main(){lmw;int t;cin>>t;while(t--){solve();}
}