\(A_i\) の取りうる値は \(M\) 通りしかありません。したがって、途中からは同じ数列を繰り返します。

• 繰り返しが始まるまでの項数とその和
• 繰り返しの項数とその和

を計算しておき、繰り返しに入るまでの和、繰り返し部分の和、繰り返し1周に満たない最後の部分の和、の3つに分けて計算することで、\(O(M)\)で解けました。繰り返しに入る前に \(N\) 項目に到達するケースに注意してください。

\( \)

例：\(M=449, A_1=2,N=1000\) のとき

\(A=\{2,4,16,256,431,324,359,18,324,359,\ldots\}\)　であり

• 繰り返しが始まるまでの部分 …… \(\{2,4,16,256,431\}\)
• 繰り返し部分…… \(\{324,359,18\}\)

なので、\(1000\) 項目までの和は \((2+4+16+256+431) + (324+359+18)\times 331 + (324+359)\)と求められます。