2021HDU多校9 - 7073 Integers Have Friends 2.0(随机数)

题目链接：点击查看

题目大意：给出一个长度为 $n$ 的序列，找到一个长度最长的子序列，满足存在一个模数 $m$，使得这个子序列中的所有数取模后相等

题目分析：挺有意思的一道题，首先假如取 $m=2$ 的话，那么所有数字非奇即偶，所以答案至少是 $\lceil \frac{n}{2}\rceil$

假如我们随机选两个位置 $x,y$，满足 $x\ne y$，那么这两个位置同时位于答案中的概率至少为 $\frac{1}{4}$，也就是说选不中的概率为 $\frac{3}{4}$

再假如我们选择的 $x$ 和 $y$ 属于答案中，那么 $m$ 可行的取值是 $|(a_x-a_y)$，筛出质因子后每次 $O(n)$ 去计算答案就可以了

那么对上述操作执行 $K$ 次，每次都选不中答案的概率就是 $(\frac{3}{4}{)}^K$，当 $K=40$ 时，这个数值就是 $10^{-5}$ 级别的了

需要注意的是，答案记得初始化为 $ans=1$，因为上面的操作只能计算答案大于等于二的情况

因为 HDU 的上古评测机，还是建议打个欧拉筛优化一下筛质因子的过程，能快不少

代码：

// Problem: Integers Have Friends 2.0 // Contest: Virtual Judge - HDU // URL: https://vjudge.net/problem/HDU-7073 // Memory Limit: 262 MB // Time Limit: 5000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; mt19937_64 eng(time(NULL)); LL a[N]; int n; int cal(LL x,LL y) {int cnt=0;for(int i=1;i<=n;i++) {cnt+=a[i]%x==y;}return cnt; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--) {scanf("%d",&n);uniform_int_distribution<int>ran(1,n);for(int i=1;i<=n;i++) {scanf("%lld",a+i);}int ans=1;for(int K=1;K<=30;K++) {int l=-1,r=-1;while(l==r) {l=ran(eng),r=ran(eng);}LL tmp=llabs(a[l]-a[r]);for(int i=2;1LL*i*i<=tmp;i++) {if(tmp%i==0) {ans=max(ans,cal(i,a[l]%i));while(tmp%i==0) {tmp/=i;}}}if(tmp>1) {ans=max(ans,cal(tmp,a[l]%tmp));}}printf("%d\n",ans);}return 0; }

总结

以上是生活随笔为你收集整理的2021HDU多校9 - 7073 Integers Have Friends 2.0(随机数)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。