AOJ 0114 Electro-Fly

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0114

解法
(x,y,z) = (1,1,1)
を
{x' = a1*x mod m1
{y' = a2*y mod m2
{z' = a3*z mod m3
で計算していくと、再び(1,1,1)になるという条件から
xだけでみたとき、xが再び1になるまでの計算回数
yだけでみたとき、yが再び1になるまでの計算回数
zだけでみたとき、zが再び1になるまでの計算回数
の最大公倍数をとってやればいいことが分かる。
32bit整数で収まるかよくわからないから long long 使っておいた

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
ll gcd(ll a, ll b){
	return (a==0)?b:gcd(b%a,a);
}
ll lcm(ll a, ll b){
	return a * b / gcd(a, b);
}

ll solve(ll a, ll m){
	ll x = 1, i;
	for(i=0; i==0 || x!=1; i++){
		x = (a*x)%m;
	}
	return i;
}
int main(){
	ll a1, a2, a3, m1, m2, m3;
	while(scanf("%lld %lld %lld %lld %lld %lld", &a1, &m1, &a2, &m2, &a3, &m3)){
		if(a1 == 0) break;
		ll xn, yn, zn;
		xn = solve(a1, m1);
		yn = solve(a2, m2);
		zn = solve(a3, m3);
		printf("%lld\n", lcm(lcm(xn, yn), zn));
	}
	return 0;
}