2/28

競技プログラミング

キャディコン(ABC193) E 

E - Oversleeping

脳内辞書で
- 無限に周期をもつ列に対してはダブリング の横に
- 無限に周期をもつ列に対しては拡張ユークリッド(中国剰余定理)
が追加された

ある長さの周期Aに対してB進む動作だけでK(mod A)進みたい
-> nB - xA = K
拡張ユークリッドの互除法(ただしKがGCD(A, B)の倍数でない場合は一生すれ違う)

今回の問題は二つの周期がともに動く問題だったが片方を固定してもう片方の列で周期Bずつ進むと考えればよかった
周期が出てきたらもう円で考えておいいのでは？と思ったが、これは保留

他: 
https://qiita.com/akebono-san/items/f00c0db99342a8d68e5d
https://wiki.kimiyuki.net/%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AB%E3%81%8A%E3%81%91%E3%82%8B%E5%85%B8%E5%9E%8B%E3%81%AE%E4%B8%80%E8%A6%A7
https://drken1215.hatenablog.com/entry/2021/01/04/010400
(↑これは拡張ユークリッドあんまり関係ないけど、周期性と約数の関係で)