atcoder.jp 解法 愚直に数列を前から順に見ていこうとすると、計算量はO(N)になり、N ≦ 1010の制約では、時間がかかりすぎてしまう。 なので、計算量を落とす方法を考える必要がある。 mod 〇〇で考えられる問題で鳩ノ巣原理が使えるというのは典型。 この問…

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