atcoder.jp 解法 Kの倍数かどうかがわかればよいので、 は mod Kで考えてよい。 さらに、 という数列を順に調べることをK+1回繰り返せば、鳩ノ巣原理で必ずループが始まる。 そのため、 という数列を順に調べることをK回繰り返して、その中にKの倍数があれば…

atcoder.jp 解法 $ A_i B_i $はなるべく小さい方が数列Bの総和は小さくなる。 数列Aの要素にそれぞれ適当な値をかけて、全て同じ値を作り出したいのだから、$ A_i B_i $は数列Aの要素の最小公倍数にすると最小になることがわかる。 最小公倍数はとんでもなく…