AOJ - Problem 0114 : Electro-Fly

• 問題文

x,y,zがそれぞれ何回で1に戻ってくるか計算し、その回数をa,b,cとするとa,b,cの最小公倍数が答えになるようです。long int(32bit)ではオーバーフローするので注意が必要です。

#include <iostream>
using namespace std;

typedef long long int ll;

ll gcd(ll a, ll b){
	return (b > 0)? gcd( b , a%b ) : a ;
}

ll lcm(ll a, ll b){
	return a / gcd(a,b) * b;
}

int main(){
	ll a1, a2, a3, m1, m2, m3;
	while( cin >> a1 >> m1 >> a2 >> m2 >> a3 >> m3 , a1||m1||a2||m2||a3||m3 ){
		ll x, y, z, a, b, c;
		a = b = c = x = y = z = 1;
		x = (x * a1) % m1;
		y = (y * a2) % m2;
		z = (z * a3) % m3;
		for( ; x != 1 ; a++ ){
			x = (x * a1) % m1;
		}
		for( ; y != 1 ; b++ ){
			y = (y * a2) % m2;
		}
		for( ; z != 1 ; c++ ){
			z = (z * a3) % m3;
		}
		ll ans = lcm( lcm(a,b) , c);
		cout << ans << endl;
	}
}