コードはそこまで長くない。
https://yukicoder.me/problems/no/2183
問題
有理数u=p/qに対応する点からなるグラフを考える。
(p+1)/(q+1)を約分してu'=p'/q'となったとき、uとu'に辺を張ることとする。
このグラフを、r=(10^100-1)/(10^100)に対応する点を根とする根付き木とみなす。
2つの有理数が与えられるので、このグラフにおいて両有理数に対応する点のLCAとなる点を求めよ。
解法
約分が生じるタイミングまで、辺の遷移を一気に行おう。
約分が生じるのは、p,qが(q-p)の約数と2以上の公約数を持つケースである。
よって最初に(q-p)の約数を列挙していこう。
int T; ll P1,Q1,P2,Q2; const int prime_max = 32000; vector<int> prime; int NP,divp[prime_max]; void cprime() { if(NP) return; for(int i=2;i<prime_max;i++) if(divp[i]==0) { //M[i]=NP; prime.push_back(i); NP++; for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i; } } void solve() { int i,j,k,l,r,x,y; string s; cprime(); cin>>T; while(T--) { cin>>P1>>Q1>>P2>>Q2; while(P1!=P2||Q1!=Q2) { if(Q1-P1<Q2-P2) swap(P1,P2),swap(Q1,Q2); if(Q1-P1==Q2-P2&&P1>P2) swap(P1,P2),swap(Q1,Q2); ll D=Q1-P1; ll cand=D-(Q1%D); if(D==1) cand=1LL<<30; if(Q1-P1==Q2-P2) { ll a=Q2-P2; ll b=Q1*P2-P1*Q2; cand=min(cand,(b+a-1)/a); } FORR(p,prime) if(D%p==0) { cand=min(cand,p-Q1%p); if(p<D) cand=min(cand,D/p-Q1%(D/p)); } ll g=__gcd(P1+cand,Q1+cand); //cout<<P1<<" "<<Q1<<" "<<P2<<" "<<Q2<<" "<<g<<" "<<P1+cand<<" "<<Q1+cand<<endl; P1=(P1+cand)/g; Q1=(Q1+cand)/g; } cout<<max(P1,P2)<<" "<<max(Q1,Q2)<<endl; } }
まとめ
考察が終われば実装は軽め?