【数学一本通 第一章】SEJ-Strongbox [LUOGU] [POI2011]

密码 [SEJ-Strongbox ]

题目链接：密码 [SEJ-Strongbox ]
（这是一道数论蓝题，想了好长时间啊~~）
【题目大意】
有一个密码箱，0到n-1中的某些整数是它的密码。且满足：如果a和b都是它的密码，那么(a+b)%n也是它的密码(a,b可以相等，%表示整除取余数)，某人试了k次密码，前k-1次都失败了，最后一次成功了。
问：该密码箱最多有多少不同的密码。
【样例】

输入：

42 5
28 31 10 38 24

输出：

14

【题解】：

首先从题目中的出的两个结论：

结论一：

如果x为密码，那么$gcd（x,n）$也是密码。

证明：

因为x是密码，由题意得2x%n,3x%n……kx%n都是密码。
由于不定方程$ax+by=c$有整数解的充要条件是$gcd(a,b)|c$，所以 $xk+nc=gcd（x,n）$一定有整数解，那么$?k\in Z$使$kx\equiv gcd（x，y）(modn)$，故gcd（x,n）也是密码。

结论二：

如果x,y为密码，那么$gcd（x,y）$也是密码。

证明：

由题意得：以为x，y是密码，显然（px+qy）% n也是密码，因为$xp+yq=gcd（x，y）$一定有整数解，那么$?p,q\in Z$使得$px+qy\equiv d(modn)$，故$gcd（x,y）$也是密码。

再看看这道题，设 $x,y$ 均为密码且x是所有密码中最小的，若$x?y$，则$gcd(x,y)<x$且 gcd(x,y) 是密码（结论二），与假设矛盾，故 $x|y$。因此，这组密码为$x,2x,3x,?,kx(kx<n)$
设$d=gcd(mk,n)$,由于$mk$是密码，根据结论一，d 也是密码，又由①得：$x|d$（仍设x是所有密码中最小的那个）

但是这道题给了一些限制条件：

1. 要求最多有多少密码，故我们希望x尽量的小，密码数量为n/x
2. 给出了k?1个不是密码的数字，故 x 不能整除 m1,m2,?,mk?1
   综上所述，这道题的实现方法是：在根号的时间里暴力枚举处理出 gcd(mk,n) 的所有因数，去除能整除 m1,m2,?,mk?1 中任意一个的数，设剩下的数中最小的为x，则答案就是 n/x

AC代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int sea=250010;
LL a[sea],q[sea],f[sea],n,k,tot=0,ans;
LL gcd(LL a,LL b){
    if(a<b) swap(a,b); return b?gcd(b,a%b):a;}
int main()
{
    scanf("%lld%lld",&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(LL i=1;i*i<=a[k];i++)if(a[k]%i==0) {
    q[++tot]=i;if(i!=a[k]/i) q[++tot]=a[k]/i;}sort(q+1,q+tot+1);for(int i=1;i<k;i++)f[lower_bound(q+1,q+tot+1,a[i])-q]=1;for(int i=1;i<=tot;i++)if(f[i])for(int j=1;j<i;j++)if(q[i]%q[j]==0) f[j]=1;ans=1; while(f[ans]) ans++;printf("%lld\n",n/q[ans]);return 0;
}

continue……