BZOJ2277 [Poi2011]Strongbox 【数论】

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 1000005,maxm = 10000005,INF = 1000000000;
inline LL read(){
    LL out = 0,flag = 1; char c = getchar();
    while (c < 48 || c > 57){if (c == ‘-‘) flag = -1; c = getchar();}
    while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
    return out * flag;
}
LL n,k,a[maxn],L,fac[maxn],p[maxn],tot,cnt;
int vis[maxn];
LL gcd(LL a,LL b){return b ? gcd(b,a % b) : a;}
void getfac(){
    LL 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 getp(){
    LL 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(){
    n = read(); k = read();
    REP(i,k) a[i] = read();
    L = gcd(n,a[k]);
    getfac(); getp();
    LL 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++){
            LL 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;
            }
        }
    }
    LL ans = 0;
    for (int i = 1; i <= tot; i++)
        if (!vis[i]){ans = n / fac[i]; break;}
    printf("%lld\n",ans);
    return 0;
}