■A - Tax Included Price
100円周期。
■B - Village of M People
二分探索
| b/m-a/n | <=xは扱いにくいので |
任意のiに対して|bn-am|<=x/(n*m)となる最小のxを求める。
bは負にならないことに注意。
構築は一旦全て最小で作って、余った分を適当に振り分けるイメージ
■C - Coprime Set
最大ケースを見ると1/4を含む必要がある。
2,3,5をベースに考え
素因数に上記の３つの素数のうち２つ以上を含む整数を小さい方から列挙するといい
6,10,12,15,18,20.....
しかしこれだとn = 3の時にgcdが2になるので細工をする。
■D - Hamiltonian Cycle
群論
サンプル１で考えると
1,4,3,12,9,10,1
5,7,2,8,6,11,5
12,9,10,1,4,3,12
8,6,11,5,7,2,8
1,4,3,12,9,10,1
となる(右移動が*4、左移動が*5に対応している)
上の図でいうところの
2*6の区間と4*3の区間を
最後に1に戻るようにひと筆書きすれば良い事がわかるので
構築をする。
