[P3518]strongbox

原题链接

题面是英文的
总之可以用谷歌翻译糊弄一下

要解决这个题一共需要两个结论

结论一：
如果x是密码
那么GCD（x , n）也是密码

结论二：
如果x , y是密码
那么GCD（x , y）也是密码

具体推导过程可以参考一下vinci的博客

那么
设密码集合A
输入的密码为a[1…k]
A中所有数的GCD为x
如果A中有比x小的数y
那么GCD（x , y）< x
不符合设定
所以x是A中最小的数

则A中的数为x , 2x , 3x……

约束条件：

由结论一可得
A中有两个数为a[k] , GCD（n , a[k]）
所以x%GCD( n , a[k] )=0

且由题意可得
对于任何1<=j< k
x % a[j] ! = 0

#include<algorithm>
#include<cstdio>
#define LL long long
using namespace std;

LL n,k,i,a[500000],tot,q[1000005],f[1000005],ans,j;

LL gcd(LL x,LL y)
{
    return y?gcd(y,x%y):x;
}

int main()
{
    scanf("%lld%lld",&n,&k);

    for(i=1;i<=k;i++)
        scanf("%lld",&a[i]);

    a[k]=gcd(a[k],n);

    for(i=1;i<k;i++)
        a[i]=gcd(a[i],a[k]);

    for(i=1;i*i<=a[k];i++)
    {
        if(a[k]%i==0)
        {
            tot++;
            q[tot]=i;

            if(i*i!=a[k]) 
            {
                tot++;
                q[tot]=a[k]/i;  
            }
        }
    }

    sort(q+1,q+tot+1);

    for(i=1;i<k;i++)
        f[lower_bound(q+1,q+tot+1,a[i])-q]=1;

    for(i=1;i<=tot;i++)
        if(f[i])
            for(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;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：[P3518]strongbox，转载请注明来源！