CF1781 D. Many Perfect Squares [数学题]

本文主要是介绍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;
}

这篇关于CF1781 D. Many Perfect Squares [数学题]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---