問題はこちらです
周期性を使った解説が多いので、ダブリングを使って解いていきます。 自力でACできなかったのでこちらの記事を参考にしました。
遷移後の値を管理する配列と、操作後の総和を管理する配列の2つを用意するところが通常のダブリングとは違うところです。
N,X,M = map(int,input().split())
SUM = [[0]*M for _ in range(35)]
nex = [[0]*M for _ in range(35)]
for j in range(1,M):
SUM[0][j] = j
nex[0][j] = pow(j,2)%M
for i in range(1,35):
for j in range(1,M):
SUM[i][j] = SUM[i-1][j] + SUM[i-1][nex[i-1][j]]
nex[i][j] = nex[i-1][nex[i-1][j]]
ans = 0
ind = X
i = 0
while N:
if N&1:
ans += SUM[i][ind]
ind = nex[i][ind]
N >>= 1
i += 1
print(ans)
