AOJ0114
問題:Electro-Fly
mod取ってぐるぐる循環する奴が1周回るのにどれだけかかるかを求める問題。
愚直なループだとTLEするので、x,y,z別に求めてそれの最小公倍数で良い。
O(1)で求める解法ありそうだけどしらん。
#include<iostream> using namespace std; template<class t> t gcd(t a, t b){ return b != 0 ? gcd(b, a % b) : a; } template<class t> t lcm(t a, t b){ return a*b/gcd(a,b); } int main() { long long a,b,c,m1,m2,m3; while( cin >> a >> m1 >> b >> m2 >> c >> m3 , a|b|c|m1|m2|m3 ) { long long x=a%m1,y=b%m2,z=c%m3,c1=1,c2=1,c3=1; while( x!=1 ){ x=(x*a)%m1; c1++; } while( y!=1 ){ y=(y*b)%m2; c2++; } while( z!=1 ){ z=(z*c)%m3; c3++; } cout << lcm(c1 , lcm( c2,c3 ) ) << endl; } }