题目描述
有一个密码箱，0到n-1中的某些整数是它的密码。 且满足，如果a和b都是它的密码，那么(a+b)%n也是它的密码(a,b可以相等) 某人试了k次密码，前k-1次都失败了，最后一次成功了。 问：该密码箱最多有多少不同的密码。
输入格式
第一行n，k
下面一行k个整数，表示每次试的密码
保证存在合法解
输出格式
一行，表示结果
输入样例
42 5
28 31 10 38 24
输出样例
14
提示
1<=k<=250000 k<=n<=10^14
分析
首先不可能存在存在两个密码互质（这一点想了我半天
如果有两个密码互质，那么0到n-1就都是密码
证明
设两个密码分别为a，b，根据扩展欧几里得定理，以下方程肯定有解
$$ax+by=1$$
从而得知以下方程有解
$$ax+byequiv1(mod n)$$
虽然题目中只能用加法，x与y可能小于0，但是因为
$$a(x+kn)+b(y+kn)equiv ax+byequiv1(mod n)$$
我应该是第一个在模运算中用连等的人
所以可以推出，如果有两个互质的密码，那么1也是密码
那么通过1自己加自己可以得出0到n-1都是密码
所以不存在互质的密码
用刚才的方法还可以一般性地证明，对于两个密码a与b，gcd(a,b)一定是密码
可以把gcd(a,b)看成万恶之源，它的倍数都是密码，进而衍生出了所有的密码。
如果一个数不是密码，那么它就绝对不是那个最小gcd的倍数
所以我们可以去枚举最小的gcd，验证是否可行。
显然gcd越小越好。
两种思路，一种是枚举后一个个验证，另一种是先去掉前k-1个数的约数再枚举。
Code 1
#include<cstdio>
#include<algorithm>
using namespace std;
int k;long long n,a[250005],ans;
long long gcd(long long a,long long b){return !b?a:gcd(b,a%b);}
int check(long long x)
{
for(int i=1;i<=k;i++)if(a[i]%x==0)return 0;
return 1;
}
int main()
{
scanf("%lld%d",&n,&k);
for(int i=1;i<=k;i++)scanf("%lld",&a[i]),a[i]=gcd(a[i],n);long long x=a[k];
sort(a+1,a+k);k=unique(a+1,a+k)-a-1;
for(long long i=1;i*i<=x;i++)if(x%i==0)
{
if(check(i)){printf("%lld
",n/i);return 0;}
if(check(x/i))ans=n/(x/i);
}
printf("%lld",ans);
}
Code 2
#include<cstdio>
#include<algorithm>
using namespace std;
int k;
long long n,en,cnt,ans,a[250005],p[250005],q[250005],pri[250005];
inline long long gcd(long long a,long long b){return !b?a:gcd(b,a%b);}
int main()
{
scanf("%lld%d",&n,&k);
for(int i=1;i<=k;i++)scanf("%lld",&a[i]);
a[k]=gcd(a[k],n);
for(int i=1;i<k;i++)a[i]=gcd(a[i],a[k]);
for(int i=1;1ll*i*i<=a[k];i++)if(a[k]%i==0)
{q[++en]=i;if(1ll*i*i!=a[k])q[++en]=a[k]/i;}sort(q+1,q+1+en);
long long x=a[k];
for(int i=2;1ll*i*i<=x;i++)if(x%i==0){pri[++pri[0]]=i;while(x%i==0)x/=i;}
if(x!=1)pri[++pri[0]]=x;
for(int i=1;i<k;i++)p[lower_bound(q+1,q+en+1,a[i])-q]=1;
for(int i=en;i>=1;i--)
{
if(p[i])
for(int j=1;j<=pri[0];j++)
if(q[i]%pri[j]==0)p[lower_bound(q+1,q+en+1,q[i]/pri[j])-q]=1;
}
cnt=1;while(p[cnt])cnt++;
printf("%lld
",n/q[cnt]);
}