[文章目录]
Description
给定n个正整数，从中挑出k个数，满足：存在某一个m(m>=2)，使得这k个数模m的余数相等。求出k的最大值，并求出此时的m。如果有多组解使得k最大，你要在此基础上求出m的最大值,n<=10^5,w<=10^7
题解别人说的都好好啊。
第一问：我们随机选一个数，假设在解里，将n个数都减去这个数，差的约数即为可以选这个数的m的范围。所以我们将所有的差质因子分解，质因子在数中存在的次数最多就是k。
蒟蒻表示将10^7分解质因数不会log的方法。。。
就是在分解质因数的时候，记录每个数的最小质因子的大小。然后，就变成log级别的了。
看了claris的题解，发现时间复杂度好像比我少个log。加了hash判断数集是否相同，每个数随机一个hash值，然后每个质数为可行的数的hash值得亦或和。两个质数的数集hash值相同的话基本可以判断两个数集相同。加一个log的算法就是直接在求出解集中所有差的gcd。然后，每次更新答案。
随机了20次，57s卡过。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,w[101000];
int ans1,ans2,num[700000],ans[700000];
int prime[700000],cnt,yz[10001000];
bool v[10001000];
int gcd(int x,int y)
{
return y==0 ? x:gcd(y,x%y);
}
void read(int &x)
{
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
}
void quick_prime()
{
for(int i=2;i<=10000000;i++)
{
if(!v[i]) prime[++cnt]=i,yz[i]=cnt;
for(int j=1;j<=cnt&&i*prime[j]<=10000000;j++)
{
v[i*prime[j]]=1; yz[i*prime[j]]=j;
if(i%prime[j]==0) break;
}
}
}
void work(int x)
{
if(x<0) x=-x; int c=x;
while(x!=1)
{
int t=yz[x]; num[t]++; ans[t]=gcd(c,ans[t]);
t=prime[t];
while(x%t==0) x/=t;
}
}
int main()
{
quick_prime();
read(n);
for(int i=1;i<=n;i++) read(w[i]);
int t=20;
while(t--)
{
memset(num,0,sizeof(num));
memset(ans,0,sizeof(ans));
int val=w[rand()%n+1],now=0,tmp=0,k;
for(int i=1;i<=n;i++)
if(w[i]==val) now++;
else work(val-w[i]);
for(int i=1;i<=cnt;i++)
if(num[i]+now>ans1) ans1=num[i]+now,ans2=ans[i];
else if(num[i]+now==ans1) ans2=max(ans2,ans[i]);
}
printf("%d %d",ans1,ans2);
return 0;
}