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;
	}
}