AOJ 0114: Electro-Fly

解けてないです

1 == a^n mod m (^はXORじゃないほう)

となる最小のnを求める問題だと思う。
このコードを提出してみたら、遅すぎって怒られた。1.18秒から0.18秒減らさないといけない。
*1もしかすると最小公倍数をもっと効率良く求められるのかもしれない。

int f(int n[]);　//最小公倍数を求めてる

int main(){
	int a[3],m[3];
	while(true){
		scanf("%d %d %d %d %d %d",&a[0],&m[0],&a[1],&m[1],&a[2],&m[2]);
		if(!a[0] && !m[0] && !a[1] && !m[1] && !a[2] && !m[2]) break;
		int res[3] ={0};
		int v[3] = {1,1,1};
		for(int i = 0; i < 3; i++){
			while(true){
				res[i]++;
				if(1 == (v[i] = (v[i] * a[i]) % m[i])) break;
			}
		}
		printf("%d\n",f(res));
	}
		
	return 0;
}

int f(int n[]){
	int p[3];
	p[0]=n[0];p[1]=n[1];p[2]=n[2];
	sort(p, p + 3);
	for(int k = 0; k < 2; k++){
		int g = 1;
		for(int i = 2; i <= p[k]; i++){
			while(p[k] % i == 0 && p[k+1] % i == 0){
				p[k]   /= i;
				p[k+1] /= i;
				g *= i;
			}
		}
		p[k+1] = n[k]*n[k+1]/g;
		if(k == 0) n[k+1] = p[k+1];
	}
	return p[2];
}

*1:追記：ユークリッドの互除法のほうが遥かに速いそうです