Edit

【pythonでABC179を解説】E - Sequence Sum

問題概要

問題ページ

問題文

\(x\) を \(m\) で割った余りを \(f(x,m)\) と表します。

初期値 \(A_1=X\) および漸化式 \(A_{n+1}= f(A_n^2, M)\) で定まる数列を \(A\) とします。\(\displaystyle{\sum_{i=1}^N A_i}\) を求めてください。

制約

  • \(1 \leq N \leq 10^{10}\)
  • \(0 \leq X < M \leq 10^5\)
  • 入力は全て整数

問題の考察

ACコード

import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, x, m = list(map(int, readline().split()))
    d = collections.defaultdict(int)
    ac = [0]
    cnt = 0
    for i in range(n):
        ac.append(x)
        ac[i + 1] += ac[i]
        if x not in d:
            d[x] = i + 1
        else:
            sm = ac[i] - ac[d[x]]
            rem = (n - i - 1) // (i + 1 - d[x])
            last = (n - i - 1) - rem * (i + 1 - d[x])
            print(ac[i + 1] + (ac[i + 1] - ac[d[x]]) * rem + (ac[d[x] + last] - ac[d[x]]))
            exit()
        x = pow(x, 2, m)
    print(ac[-1])


if __name__ == '__main__':
    solve()

-Edit
-