1597:Uniform Generator

PKU

keyword

線形合同法　シミュレーション　C++

概要

線形合同法の係数と種が与えられたとき、全ての数が表れるかどうかを判定する問題。
gcd使って簡単にO(1)で求まりそうな気もするけどシミュレーションで間に合うので愚直に試した。

int main(){
    int st, mod, cur, i;
    char good[] = "Good Choice", bad[] = "Bad Choice";
    bool occurred[100000];

    while(scanf("%d%d",&st,&mod)!=EOF){
        REP(i,100000) occurred[i] = false;
        for(cur=0;!occurred[cur];occurred[cur]=true,cur = (cur+st)%mod);
        printf("%10d%10d    %s\n\n",st,mod,count(occurred,occurred+mod,true)==mod?good:bad);
    }

    return 0;
}