AOJ0114 Electro-Fly

問題リンク Electro-Fly

• 解法

サンプルを見ての通り、x', y', z'を逐一計算していくと実行時間がとんでもないことになります。
まずx,y,zを個別に考えて、それぞれ何回計算を行ったら1に戻ってくるかを計算します。xについてx1回の計算で1に戻ってきたとすると2*x1回でも、3*x1回でも1に戻ってくることになります。y,zも同様です。求めたいのはxもyもzも1に戻ってくる最小の回数なのだからこれらの最小公倍数が答えになります。
正直にいうと、3つの数の最小公倍数の求め方は知らなかったので、2数の最小公倍数の式a*b/gcd(a,b)をもとにぐしゃぐしゃやってたらソースのようになりました。もっとスマートに書けるかもしれません。

• ソース

import java.util.Scanner;

//Electro-Fly
public class AOJ0114 {

	public static long gcd(long a, long b){
		if(a < b){
			long tmp = a;
			a = b;
			b = tmp;
		}
		while(b!=0){
			long r = a%b;
			a = b;
			b = r;
		}
		return a;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int a1 = sc.nextInt();
			int m1 = sc.nextInt();
			int a2 = sc.nextInt();
			int m2 = sc.nextInt();
			int a3 = sc.nextInt();
			int m3 = sc.nextInt();
			if((a1|a2|a3|m1|m2|m3)==0)break;
			long x1 = 1;
			long x2 = 1;
			long x3 = 1;
			int x = a1%m1;
			int y = a2%m2;
			int z = a3%m3;
			while(x!=1){
				x1++;
				x = (x*a1)%m1;
			}
			while(y!=1){
				x2++;
				y = (y*a2)%m2;
			}
			while(z!=1){
				x3++;
				z = (z*a3)%m3;
			}
			System.out.println(x1*x2/gcd(x1, x2)*x3/gcd(x2,x3)/gcd(x1,x3)*gcd(x1, gcd(x2,x3)));
		}
	}
}