[HOJ 158][POI 18 Stage 2]猜密碼

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

仔細想就會發現，如果x和y都是密碼，那麼任何(ax+by)%N (a、b為任意非負整數) 的形式也都會是密碼
PW是一個已知密碼，所以每隔Gcd(PW,N)就會出現循環(假如我們用0和1代表是不是密碼)
如果有任何一個猜錯的密碼被Gcd(PW,N)整除，那答案就是1了
再來就是怎麼算這長度為Gcd(PW,N)的01序列
現在我們把視野範圍縮小到這長度為Gcd(PW,N)的01序列，可以發現，如果f是密碼，那麼任何整除Gcd(f,Gcd(PW,N))的數也都會是密碼，因此我們可以從小到大枚舉這個Gcd(f,Gcd(PW,N))，也就是gap，找到第一個不和非密碼數們衝突的gap，然後就可以知道這個01序列就是每隔gap的長度就會出現一個1的形式了
雖然可以直接算出N/gap，可是繼承先前的思路我是先算出n/gap再乘上N/n XD
對了，那個lower_bound的優化很重要

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
LL Gcd(const LL &a,const LL &b){return b==0LL?a:Gcd(b,a%b);}
LL N,S[250000],PW;
int K;
LL Solve(const LL &n)
{
//    printf("n=%lld\n",n);
    for(int i=0;i<K;i++)S[i]=Gcd(S[i],n);
    sort(S,S+K),K=unique(S,S+K)-S;
    assert(K==0||S[0]>0LL);
    vector<LL>factor;
    for(LL gap=1LL;gap*gap<=n;gap++)if(n%gap==0LL)
    {
        if(gap*gap<n)factor.push_back(n/gap);
        bool found=false;
        for(int i=lower_bound(S,S+K,gap)-S;i<K;i++)if(S[i]%gap==0){found=true;break;}
        if(!found)return n/gap;
    }
    for(int i=(int)factor.size()-1;i>=1;i--)
    {
        const LL &gap=factor[i];
        bool found=false;
        for(int i=lower_bound(S,S+K,gap)-S;i<K;i++)if(S[i]%gap==0){found=true;break;}
        if(!found)return n/gap;
    }
    factor.clear();
    vector<LL>().swap(factor);
    return 1LL;
}
LL Solve()
{
    LL gap=Gcd(N,PW);
    for(int i=0;i<K;i++)if(S[i]%gap==0LL)return 1LL;
    return Solve(gap)*(N/gap);
}
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%lld%d",&N,&K),K--;
    for(int i=0;i<K;i++)scanf("%lld",&S[i]);
    scanf("%lld",&PW);
    printf("%lld\n",Solve());
    return 0;
}