yukicoder : No.356 円周上を回る3つの動点の一致

ラスト10分しか参加できなかった上、マスターマインドで手間取って終了。
http://yukicoder.me/problems/616

問題

1周の長さがLの円周上を3つの点が時計回りに回っている。
それぞれの周期はT[1],T[2],T[3]である。

3点の位置が一致するタイミングがあった場合、次に3点の位置が一致するまでの最短時間を求めよ。

解法

点の移動速度はそれぞれ。
最初の2点の移動速度の差はより、この2点が次に重なるのは後。
同様に1点目と3点目が次に重なるのは後。

後はこれらの最小公倍数を取ろう。
途中でオーバーフローしないように注意。

int T[3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,3) cin>>T[i];
	__int128 a=T[0]*T[1];
	__int128 b=T[1]-T[0];
	__int128 g=__gcd(a,b);
	a/=g;
	b/=g;
	__int128 c=T[0]*T[2];
	__int128 d=T[2]-T[0];
	g=__gcd(c,d);
	c/=g;
	d/=g;
	
	a*=d;
	c*=b;
	b*=d;
	a=a/__gcd(a,c)*c;
	g=__gcd(a,b);
	a/=g;
	b/=g;
	_P("%lld/%lld\n",abs((ll)a),abs((ll)b));
	
	
}

まとめ

マスターマインドの方が手こずった。