题目链接:strongbox(英文版)
结论1:如果x是密码,则gcd(x,n)是密码
结论2:如果x,y是密码,那么gcd(x,y)是密码,反之则不是
约束条件:
1.密码集合A中存在很多,所以尽量小
2.对于任何1<=j<k,不能整除a[j](否则a[j]也是密码)
3.根据结论1,集合中的两个数为a[k],gcd(a[k],n),存在a[k]|gcd(a[k],n)。
思路:
如果x为密码,则密码为x,2x,3x,4x,......,所以x尽量小,n/x即为答案
同时a[k]的因子集合包含密码集合,里面也含有其它不是密码的数
其中gcd(a[i],a[k])不属于,被gcd(a[i],a[k])整除的同样不是,剩下的为密码
寻找里面最小的密码,得到答案
实现方法
计算a[k]==gcd(a[k],n),枚举法寻找a[k]的因子,存在数组q里面
去除gcd(a[i],a[k])的因数(包含本身和它的因子)
寻找最小密码x,da答案为n/x
//代码
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
ll n,tot;
int k,ans;
ll a[250005],q[250005],f[250005];
ll gcd(ll a,ll b)
{
return b? gcd(b,a%b):a;
}
int main()
{
//freopen("strong.in","r",stdin);
//freopen("strong.out","w",stdout);
scanf("%lld%d",&n,&k);
for(ll 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*i!=a[k])
q[++tot]=a[k]/i;
}
sort(q+1,q+tot+1);
//去除gcd(a[k],a[i])的因数
for(int i=1; i<k; ++i)
f[lower_bound(q+1,q+tot+1,a[i])-q]=1;
for(ll 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;
}
//寻找最小密码
for(ans=1; f[ans]; ++ans);
printf("%lld",n/q[ans]);
return 0;
}