cjb-poi2011strongbox

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define PI 3.1415926535897932384626433
#define N 200010
#define LF double
long long n,k,a[1000005],L,fac[1000005],p[1000005],tot,cnt;
int vis[1000005];
long long gcd(long long x,long long y)
{
    if (y==0)return x;
    else return gcd(y,x%y);
}
void fuck1()
{
    long long x,tmp = L;
    for (x = 1; x * x <= tmp; x++){
        if (tmp % x == 0){
            fac[++tot] = x;
            if (x * x != tmp) fac[++tot] = tmp / x;
        }
    }
    sort(fac + 1,fac + 1 + tot);
}
void fuck2()
{
    long long x,tmp = L;
    for (x = 2; x * x <=tmp; x++)
        if (tmp % x == 0){
            p[++cnt] = x;
            while (tmp % x == 0) tmp /= x;
        }
    if (tmp - 1) p[++cnt] = tmp;
}
int main()
{
    cin>>n>>k;
    rep(i,k)scanf("%lld",&a[i]);
    L = gcd(n,a[k]);
    fuck1();
    fuck2();
    long long x;
    for (int i = 1; i < k; i++)
    {
        x = gcd(a[i],L);
        vis[lower_bound(fac + 1,fac + 1 + tot,x) - fac] = true;
    }
    for (int i = tot - 1; i; i--)
    {
        if (vis[i]) continue;
        x = fac[i];
        for (int j = 1; j <= cnt && x * p[j] <= L; j++)
        {
            long long y = x * p[j];
            int pos = lower_bound(fac + 1,fac + 1 + tot,y) - fac;
            if (fac[pos] == y && vis[pos])
            {
                vis[i] = true;
                break;
            }
        }
    }
    long long ans = 0;
    for (int i = 1; i <= tot; i++)
        if (!vis[i]){ans = n / fac[i]; break;}
    cout<<ans<<endl;
    return 0;
}
}}}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define PI 3.1415926535897932384626433
#define N 200010
#define LF double
long long n,k,a[1000005],L,fac[1000005],p[1000005],tot,cnt;
int vis[1000005];
long long gcd(long long x,long long y)
{
    if (y==0)return x;
    else return gcd(y,x%y);
}
void fuck1()
{
    long long x,tmp = L;
    for (x = 1; x * x <= tmp; x++){
        if (tmp % x == 0){
            fac[++tot] = x;
            if (x * x != tmp) fac[++tot] = tmp / x;
        }
    }
    sort(fac + 1,fac + 1 + tot);
}
void fuck2()
{
    long long x,tmp = L;
    for (x = 2; x * x <=tmp; x++)
        if (tmp % x == 0){
            p[++cnt] = x;
            while (tmp % x == 0) tmp /= x;
        }
    if (tmp - 1) p[++cnt] = tmp;
}
int main()
{
    cin>>n>>k;
    rep(i,k)scanf("%lld",&a[i]);
    L = gcd(n,a[k]);
    fuck1();
    fuck2();
    long long x;
    for (int i = 1; i < k; i++)
    {
        x = gcd(a[i],L);
        vis[lower_bound(fac + 1,fac + 1 + tot,x) - fac] = true;
    }
    for (int i = tot - 1; i; i--)
    {
        if (vis[i]) continue;
        x = fac[i];
        for (int j = 1; j <= cnt && x * p[j] <= L; j++)
        {
            long long y = x * p[j];
            int pos = lower_bound(fac + 1,fac + 1 + tot,y) - fac;
            if (fac[pos] == y && vis[pos])
            {
                vis[i] = true;
                break;
            }
        }
    }
    long long ans = 0;
    for (int i = 1; i <= tot; i++)
        if (!vis[i]){ans = n / fac[i]; break;}
    cout<<ans<<endl;
    return 0;
}