問題はこちら
No.229 線分上を往復する3つの動点の一致 - yukicoder
editorialの解説がとても丁寧で、これ以外に説明の方法もないので、以下ほとんど同じことを書く
池の周りを走る算数の問題を知っていればイメージしやすいので先にその例
例題
1周3.6kmの池の周りをA君は160m/min、B君は200m/minで走る。
2人が同じ地点を同時にスタートして
(1)違う方向に走るとき、初めてすれ違うのはスタートして何分後か？
(2)同じ方向に走るとき、初めてすれ違うのはスタートして何分後か？
この問題の答えは一般に、2人の走る速さや池の周長によらず、
(1)2人の走った距離の和が1周分になったとき
(2)2人の走った距離の差が1周分になったとき
となることがわかり、ここからさらに
(1)違う向きに走る2人がすれ違うのは、2人が走った距離の和が周長の整数倍になった時
(2)同じ向きに走る2人がすれ違うのは、2人が走った距離の差が周長の整数倍になった時
がわかる
これを知っていれば元の問題についてi≠jのとき
(1)PiがPjとすれ違うのは、2点の移動距離の和が線分往復分の整数倍になった時
(2)PiがPjを追い越すのは、2点の移動距離の差が線分往復分の整数倍になった時
ということわかる。これは、経過時間をTとすれば
(1)(1/Ti-1/Tj)Tが整数になった時
(2)(1/Ti+1/Tj)Tが整数になった時
よって「P1,P2,P3の3点の位置が一致」⇔「P1とP3の位置が一致、かつ、P2とP3の位置が一致」であることから
isint(x)でxが整数か否かを表すとすれば
(isint( (1/T1-1/T3)T ) or isint( (1/T1+1/T3)T )) and (isint( (1/T2-1/T3)T) or isint( (1/T2+1/T3)T ))
がTRUEとなるような最初のTを求めることとなる
分解して
(isint( (1/T1-1/T3)T ) and isint( (1/T2-1/T3)T )) or
(isint( (1/T1-1/T3)T ) and isint( (1/T2+1/T3)T )) or
(isint( (1/T1+1/T3)T ) and isint( (1/T2-1/T3)T )) or
(isint( (1/T1+1/T3)T ) and isint( (1/T2+1/T3)T ))
一般に3つの整数X,Y,Z(Z≠0）に対し
「isint( X/Z*T ) and isint( Y/Z*T )」がTRUEとなる最小TはZ/GCD(X,Y)であるので、A:=T1*T2*T3とおけば
isint((1/T1-1/T3)T) and isint((1/T2-1/T3)T)
=isint((T3-T1)*T2/A*T) and isint((T3-T2)*T1/A*T) （値を通分して計算しただけ）
より、これをが真になる最小のTはA/GCD((T3-T1)*T2,(T3-T2)*T1) となる
他の3つも同様に計算する
long gcd(long p,long q){ if(q==0)return p; else return gcd(q,p%q); } int main(){ long t1,t2,t3,temp,m; scanf("%ld%ld%ld",&t1,&t2,&t3); //分子をt1*t2*t3で固定すれば、最大の分母を求める問題になる m=gcd((t3-t1)*t2,(t3-t2)*t1); temp=gcd((t3-t1)*t2,(t3+t2)*t1); if(temp>m)m=temp; temp=gcd((t3+t1)*t2,(t3-t2)*t1); if(temp>m)m=temp; temp=gcd((t3+t1)*t2,(t3+t2)*t1); if(temp>m)m=temp; //求める答えは(t1*t2*t3)/m これを約分する temp=gcd(t1*t2*t3,m); printf("%ld/%ld",t1*t2*t3/temp,m/temp); }
同じような計算を何度もやってるのでとりあえずメイン部分の計算は
for(i=0;i<4;i++){temp=gcd((i&1?t3+t1:t3-t1)*t2,(i&2?t3+t2:t3-t2)*t1);…;}
という形にまとめられる
またここで求められるgcdの値は高々(t3+t1)*t2なので、最後の出力は%dでしてよい
long i,t,a,b,c; g(long p,long q){return q?g(q,p%q):p;} main(m){ for(scanf("%d%d%d",&a,&b,&c);i++<4;m=t>m?t:m)t=g((i&1?c+a:c-a)*b,(i&2?c+b:c-b)*a); t=g(i=a*b*c,m); i=!printf("%ld/%d",i/t,m/t); }
187B
2016/05/29追記
よく見たらgcdの第二引数はintでもいいじゃん
long i,t,a,b,c; g(long p,int q){return q?g(q,p%q):p;} main(m){ for(scanf("%d%d%d",&a,&b,&c);i++<4;m=t>m?t:m)t=g((i&1?c+a:c-a)*b,(i&2?c+b:c-b)*a); t=g(i=a*b*c,m); i=!printf("%ld/%d",i/t,m/t); }
186B
2017/08/12追記
gcdのreturn文を省略
long i,t,a,b,c; g(long p,int q){!q?t=p:g(q,p%q);} main(s){ for(scanf("%d%d%d",&a,&b,&c);i++<4;s=t>s?t:s)g(b*(i%2?c+a:c-a),a*(i&2?c+b:c-b)); g(i=a*b*c,s); printf("%ld/%d",i/t,s/t); }
175B
