aoj0114:Electro-Fly

問題文

http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?volumeNo=0

解法

まず、x,y,z成分それぞれについて最少何回で元の場所に戻ってくるかどうかを調べる。これは、実際にシミュレーションをしても間に合う。なぜなら、mのとりうる最大値は2^15であるので、座標のとりうる値が高々2^15であるためである。つまり、最大でも2^15回シミュレーションを行うと一度きたことのある座標に再び到達する(再び到達したときの座標は必ず1である。1でなければ無限に1には帰ってこれない)。

あとは、先ほどシミュレーションを行ったことで得られたx,y,zそれぞれについての最少何回で元の場所に戻ってくるかという値のlcmを求めれば答え。このlcmも最大で(2^15)^3=2^45くらいなのでlong long intに収まる。

コード

#include<bits/stdc++.h>
using namespace std;
#define int long long

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}

int get(int a,int m){
    int c=0,x=1;
    do{
        x=x*a%m;
        c++;
    }while(x!=1);

    return c;
}

signed main(){
    int a,b,c,l,m,n;
    while(cin>>a>>l>>b>>m>>c>>n){
        if(!a&&!b&&!c&&!l&&!m&&!n)break;
        cout<<lcm(get(a,l),lcm(get(b,m),get(c,n)))<<endl;
    }
    return 0;
}