結果
問題 | No.2183 LCA on Rational Tree |
ユーザー | tails |
提出日時 | 2023-01-17 19:48:45 |
言語 | cLay (20240104-1) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 804 bytes |
コンパイル時間 | 6,950 ms |
コンパイル使用メモリ | 221,560 KB |
実行使用メモリ | 10,724 KB |
最終ジャッジ日時 | 2023-08-30 22:59:16 |
合計ジャッジ時間 | 7,678 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 10 ms
10,724 KB |
testcase_01 | AC | 31 ms
10,500 KB |
testcase_02 | AC | 46 ms
10,636 KB |
testcase_03 | AC | 26 ms
10,508 KB |
testcase_04 | AC | 14 ms
10,496 KB |
testcase_05 | AC | 32 ms
10,528 KB |
ソースコード
ll@q; rep(q){ ll@up,@uq,uf[32],ufn,ul=0; ll@vp,@vq,vf[32],vfn,vl=0; uq-=up; vq-=vp; ufn=Factor(uq,uf); vfn=Factor(vq,vf); while(1){ ll d=vq-uq; if(d==0){ if(up<vp){ if(vp<up+ul){ wt(vp,vp+vq); break; } }else{ if(up<vp+vl){ wt(up,up+uq); break; } } } if(d<=0){ up+=ul; rep(i,ufn){ while(up%uf[i]==0&&uq%uf[i]==0){ up/=uf[i]; uq/=uf[i]; } } ul=1<<30; if(uq>1){ rep(i,ufn){ if(uq%uf[i]==0){ ll r=uf[i]-up%uf[i]; ul<?=r; } } } } if(d>=0){ vp+=vl; rep(i,vfn){ while(vp%vf[i]==0&&vq%vf[i]==0){ vp/=vf[i]; vq/=vf[i]; } } vl=1<<30; if(vq>1){ rep(i,vfn){ if(vq%vf[i]==0){ ll r=vf[i]-vp%vf[i]; vl<?=r; } } } } } }