Problem:


Score : 500 points

Problem Statement

Let us denote by f(x, m) the remainder of the Euclidean division of x by m.

Let A be the sequence that is defined by the initial value A_1=X and the recurrence relation A_{n+1} = f(A_n^2, M).
Find \displaystyle{\sum_{i=1}^N A_i}.

Constraints

1 \leq N \leq 10^{10}

0 \leq X < M \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X M

Output

Print \displaystyle{\sum_{i=1}^N A_i}.

Sample Input 1

6 2 1001

Sample Output 1

1369

The sequence A begins 2,4,16,256,471,620,\ldots Therefore, the answer is 2+4+16+256+471+620=1369.

Sample Input 2

1000 2 16

Sample Output 2

6

The sequence A begins 2,4,0,0,\ldots Therefore, the answer is 6.

Sample Input 3

10000000000 10 99959

Sample Output 3

492443256176507



Sample input:
6 2 1001


Sample output:
1369

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
list_mo = []
a_n = X

c = 0
for i in range(M):
    
    a_n_1 = (a_n ** 2) % M
    
    a_n = a_n_1
    
    if a_n_1 not in list_mo: 
        list_mo.append(a_n_1)
    else:

        break


initial = X + list_mo[0]

sum_mo = sum(list_mo[1:-1])  + list_mo[-1] 
len_loop = len(list_mo) - 1

plus_mo = sum_mo * (N // len_loop)
    
rest_ = N - 2 - ((N // len_loop) * len_loop) +1

rest_mo = sum(list_mo[0: rest_]) 

result = initial + plus_mo + rest_mo - list_mo[0]

print(result)

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split())

num_list = []
num2 = x

for i in range(n) :
    num1 = num2 % m
    if num1 in num_list :
        num = num_list.index(num1)
        break
    else :
        num_list.append(num1)
    num2 = num1 ** 2

if num_list = [] :
    primt(0)
else :
    acc1 = sum(num_list[:num])
    acc2 = sum(num_list[num:])
    
    num3 = n // len(num_list[num:])
    num4 = n % len(num_list[num:])
    print(acc1 + acc2 * num3 + sum(num_list[num : num4]))

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())

if X == 0:
    print(0)
    exit()

if N == 1:
    print(X)
    exit()

d = [-1] * (M + 1)
out = [0]
a = X
ans = 0
for i in range(1, N + 1):
    ans += a
    d[a] = i
    out.append(a)
    a = a ** 2 % M
    if a == 0:
        print(ans)
        exit()

    if d[a] != -1:
        loop_num = i + 1 - d[a]
        remain = N - i
        break
ans += sum(out[d[a]:d[a] + loop_num]) * (remain // loop_num)
ans += sum(out[d[a]:d[a] + (remain % loop_num)])

print(ans)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
l=[0]*m
s=[0]*m
t=p=0
while l[x]<1:
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
  t+=1
T=t-l[x]
S=s[p]+x-s[x]
if n<l[x]:
  print(s[l.index((n-1)%m)])
else:
  print(S*((n-l[x])//T)+s[l.index((l[x]+(n-l[x])%T-1)%m)])

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, X, mod = mapint()

s = set()
s.add(X)
s_loop = set()
ans = X
loop = 0
loops = []
for i in range(min(10**5*2+10, N-1)):
    X = pow(X, 2, mod)
    if X in s:
        if X in s_loop:
            loops.append(X)
            break
        loop += X
        s_loop.add(X)
        loops.append(X)
    s.add(X)
    ans += X

rest = N-i-2
if rest:
    ans += (rest//len(s_loop))*loop
    amari = rest%len(s_loop)+1
    for i in range(amari):
        ans += loops[i]
    print(ans)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
def main():
    N,X,M = map(int,input().split())
    dict = {key:0 for key in range(M)}
    #print(dict)
    dict[X] += 1
    cnt = 1
    A = [0]*M
    A[1] = X
    ans = X
    tmp = X
    for i in range(1,N,1):
        tmp = (tmp**2)%M
        if dict[tmp] != 0:
            break
        ans += tmp
        A[i+1] = A[i]+tmp
        cnt += 1
        dict[tmp] += cnt

    num = N - cnt#残り足す回数
    roop_num = cnt - dict[tmp] + 1
    syo = num//roop_num
    amari = num%roop_num
    ans += syo*(A[cnt]-A[dict[tmp]-1])
    ans += (A[dict[tmp]+amari-1]-A[dict[tmp]-1])
    return ans

print(main())

Submission status: Runtime Error

Solution code:
def f(x, m):
    return (x ** 2) % m


def main():
    n, x, m = map(int, input().split())
    lst = [[False, 0] for _ in range((m + 1))]
    lst[x] = [True, 1]
    res = [x]

    for i in range(2, m + 1):
        x = f(x, m)
        if lst[x][0] == False:
            lst[x][0] = True
            lst[x][1] = i
            res.append(x)
        else:
            loop = i - lst[x][1]
            non_loop = lst[x][1] - 1
            break
    if loop == 0:
        print(sum(res))
        exit()
    ans = sum(res[:non_loop])
    ans += (n - 2) // loop * sum(res[non_loop:])
    ans += sum(res[non_loop:non_loop + (n - 2) % loop])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,x,m = map(int,input().split())

if x == 0:
    print(0)
    exit()

li = [-1] * (m+1)
v = [False] * (m+1)
v2 = [False] * (m+1)
v[x] = True
tmp = x
ans = x
loop = 0
cnt = 0
cnt_l = 0
loop_li = [0]
ans_li = [x]

for i in range(m):
    li[i] = i ** 2 % m

while True:
    tmp = li[tmp]
    ans += tmp
    v[tmp] = True
    cnt += 1
    ans_li.append(ans_li[-1] + tmp)
    if v[li[tmp]]:
        break

while True:
    tmp = li[tmp]
    loop += tmp
    v2[tmp] = True
    cnt_l += 1
    loop_li.append(loop_li[-1] + tmp)
    if v2[li[tmp]]:
        break

cnt -= cnt_l - 1
loop_li = loop_li[1:]
ans_li = ans_li[:cnt]

if n < len(ans_li):
    print(ans_li[n-1])
elif n == len(ans_li):
    print(ans_li[-1])
else:
    n -= len(ans_li)
    if n % len(loop_li) == 0:
        print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)))
    else:
        print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)) + loop_li[n%len(loop_li)-1])

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, X, mod = mapint()

s = set()
s.add(X)
s_loop = set()
ans = X
loop = 0
loops = []
for i in range(min(10**5*2+10, N-1)):
    X = pow(X, 2, mod)
    if X in s:
        if X in s_loop:
            break
        loop += X
        s_loop.add(X)
        loops.append(X)
    s.add(X)
    ans += X

rest = N-i-2
if rest:
    ans += (rest//len(s_loop))*loop
    amari = rest%len(s_loop)+1
    for i in range(amari):
        ans += loops[i]
    print(ans)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
n,X,m=map(int,input().split())
x=[0]*m
y=[0]*m
y[0]=X
z=[0]*(m+1)
z[X]+=1
for i in range(1,m):
    x[i]=(i**2)%m
for i in range(1,m+1):
    y[i]=x[y[i-1]]
    z[y[i]]+=1
    if z[y[i]]==2:
        e=i
        q=y[i]
        break
for i in range(len(y)):
    if y[i]==q:
        b=i
        break
l=y[b:e]
L=len(l)
s=sum(l)
#print(x)
#print(y)
#print(z)
#print(b,e)
#print(l)
#print(sum(y[:b]))
#print(((n-b)//L)*s)
#print(sum(l[:(n-b)%L]))
if n>=b:
    ans=sum(y[:b])+((n-b)//L)*s+sum(l[:(n-b)%L])
else:
    ans=sum(y[:n])
print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.buffer.readline

n, x, mod = map(int, input().split())
ans = 0
temp = x
num = 1
# while temp < mod:
#     temp *= x
#     num += 1


A = [0] * (mod + 1)

kouho = {}
if n < mod:
    A[1] = x % mod
    ans += A[1]
    for i in range(2, n + 1):
        A[i] = A[i - 1] * A[i - 1] % mod
        ans += A[i]
        # print(ans)
else:
    A[1] = x
    ans += A[1]
    kouho[A[1]] = 1
    temp = A[1]
    for i in range(2, mod + 1):
        A[i] = temp * temp % mod
        if A[i] in kouho:
            migi = i
            break
        kouho[A[i]] = i
        temp = A[i]
    saisho = 0
    hidari = kouho[A[i]]
    saisho = sum(A[1:hidari])
    # for i in range(1, hidari):
    #     saisho += A[i]
    cycle_val = sum(A[hidari:migi])
    # cycle_val = 0
    # for i in range(hidari, migi):
    #     cycle_val += A[i]
    cycle = migi - hidari
    if cycle >= 2:

        kaisu = n // cycle
        amari = n % cycle - (hidari - 1)
        amari %= cycle
        kaisu = (n - (amari + hidari - 1)) // cycle
        amari_val = sum(A[hidari : hidari + amari])
        # amari_val = 0
        # for i in range(hidari, hidari + amari):
        #     amari_val += A[i]
        ans = saisho + cycle_val * kaisu + amari_val
    else:
        ans = 0
        if cycle == 0:
            for j in range(1, i + 1):
                ans += A[j]
        else:
            for j in range(1, i + 1):
                ans += A[j]
            ans += (n - i) * A[j]
print(ans)

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split())

def main(a):
    if a == 1:
        return x
    if a >= 2:
        return (main(a-1)**2) % m

ans = 0
for i in range(1, n+1):
    ans += main(i)
print(ans)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())

if X == 0:
    print(0)
    exit()
    
if N == 1:
    print(X)
    exit()

d = [-1] * (M + 1)
out = [0]
a = X
ans = 0
for i in range(1, N + 1):
    ans += a
    d[a] = i
    out.append(a)
    a = a ** 2 % M
    if d[a] != -1:
        loop_num = i + 1 - d[a]
        remain = N - i
        break
ans += sum(out[d[a]:d[a] + loop_num]) * (remain // loop_num)
ans += sum(out[d[a]:d[a] + (remain % loop_num)])

print(ans)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
l=[0]*m
s=[0]*m
t=p=0
while l[x]<1:
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
  t+=1
T=t-l[x]
S=s[p]+x-s[x]
if n<=t:
  print(s[l.index((n-1)%m)])
else:
  print(S*((n-l[x])//T)+s[l.index((l[x]+(n-l[x])%T-1)%m)])

Submission status: Runtime Error

Solution code:
def f(x, m):
    return (x ** 2) % m


def main():
    n, x, m = map(int, input().split())
    lst = [[False, 0] for _ in range((m + 1))]
    lst[x] = [True, 1]
    res = [x]

    for i in range(2, m + 1):
        x = f(x, m)
        if lst[x][0] == False:
            lst[x][0] = True
            lst[x][1] = i
            res.append(x)
        else:
            loop = i - lst[x][1]
            non_loop = lst[x][1] - 1
            break

    ans = sum(res[:non_loop])
    ans += (n - 2) // loop * sum(res[non_loop:])
    ans += sum(res[non_loop:non_loop + (n - 2) % loop])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N,X,M = map(int, input().split())


A = [-1]*M
A[0] = X
i = 0
tmpans = 0
flag = False
check = [-1]*(M+1)
slice = -1
while i< N-1:
    newa = A[i]**2%M
    i+= 1
    if check[newa] != -1:
        flag = True
        slice = check[newa]
        break
    A[i] = newa
    check[newa] = i

if not flag:
    print(sum(A[:i+1]))

else:
    print(sum(A[:slice])+ sum(A[slice:i])*((N-slice)//(i-slice))+sum(A[slice:slice + (N-slice)%(i-slice)]))

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split())

q = 0   #項数の数
a = x   #初期値

ans = 0

ans += a
t = []

for i in range(n - 1):
    a = a ** 2
    y = a % m
    t.append(y)

    if y == a ** 2:
        l = n // q
        r = n % q
        l = l * ans
        for j in range(r):
            ans += t[j]
            break

    ans += y
    q += 1
    y = 0

print(ans)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
l=[0]*m
s=[0]*m
t=p=0
while l[x]<1:
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
  t+=1
T=t-l[x]
S=s[p]+x-s[x]
if n<t:
  print(s[l.index((n-1)%m)])
else:
  print(S*((n-l[x])//T)+s[l.index((l[x]+(n-l[x])%T-1)%m)])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
import decimal
from decimal import Decimal
decimal.getcontext().prec = 10

from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

N, X, M = inpl()
loop = [0] * N
dp = [False] * (M + 100)
loop[0] = X
a = [0] * (M + 100)
a[0] = X
dp[X] = True
left , right = 0, 0


cnt = 0
for i in range(1, N):
    a[i] = (a[i-1] ** 2) % M
    loop[i] = loop[i-1] + a[i]
    # print(i, a[i])
    if i == N-1:
        print(loop[N-1])
        exit(0)
    if a == 0:
        print(loop[i])
        exit(0)
    if dp[a[i]]:
        for j in range(0, M+1):
            if a[j] == a[i]:
                left = j
                break
        right = i - 1
        break
    else:
        dp[a[i]] = True
cycle = right - left + 1 
num = loop[right] - loop[left - 1]
A = (N - left + 1) // cycle
B = (N - left + 1) % cycle
print(A * num + loop[left + B])

Submission status: Runtime Error

Solution code:
N,X,M = list(map(int, input().split()))

A = [X]
d = {}
d[X] = 1
for i in range(N):
  p = (A[i]**2) % M
  A.append(p)
  if(p in d):
    break
  else:
    d[p] = 1

lastkey = next(iter(reversed(d)))
ans = 0
loopflag = 0
keylist = list(d.keys())
for i in range(len(keylist)):
  if(keylist[i]**2 >= M):
    looplist = keylist[i:]
    loopflag = 1
    break
if(looplist[-1]==0):
  looplist.pop(0)
looplength = len(looplist)
#print("looplength =",looplength)
onekeylen = len(keylist) - looplength
#print(len(keylist))

loopnum = (N - 1 - onekeylen) // looplength
remain = (N - 1 - onekeylen) % looplength
#print("onekeylen =",onekeylen)
#print("loopnum =",loopnum)
#print("remain =",remain)
#print("lastkey =",lastkey)

#d[looplist[0]] -= 1
for i in range(looplength):
  d[looplist[i]] += loopnum - 1
for i in range(remain+1):
  d[looplist[i]] += 1

for i in range(len(keylist)):
  ans += keylist[i] * d[keylist[i]]
print(ans)
#print("keylist =",keylist)
#print("looplist =",looplist)
#print(d)

Submission status: Runtime Error

Solution code:
n,x,m = map(int,input().split())
ans= [2]*(n)
for i in range(n-1):
    ans[i+1] = x**2 % m
    x = ans[i+1]
print(str(sum(ans)))

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())

ans = [X]
a = X

for to in range(1, N):
    a = (a**2) % M
    if a in ans:
        break
    else:
        ans.append(a)
for fr, tmp in enumerate(ans, 0):
    if a == tmp:
        break
ret = 0
ret += sum(ans[:fr])
if fr != to:
    l = (N-fr)//(to-fr)
    ret += sum(ans[fr:to]) * l
    if N > fr + ((N-fr)//(to-fr))*(to-fr):
        m = N - (fr + ((N-fr)//(to-fr))*(to-fr))
        ret += sum(ans[fr:to][:m])
print(ret)

Submission status: Runtime Error

Solution code:
n, x, mod = map(int, input().split())
lst = [0, x]
num_set = set([x])
num_lst = [0, x]
flag = False

for i in range(mod - 1):
  x = (x * x) % mod
  s = x + lst[-1]
  if x == 0:
    lst.append(s)
    break
  if x in num_set:
    flag = True
    break
  lst.append(s)
  num_set.add(x)
  num_lst.append(x)
  if i == n:
    break

#print(lst)
if flag:
  for i, ele in enumerate(num_lst):
    if x == ele:
      loop_s = i
      break

l = len(lst)
if lst[l - 1] == lst[l - 2]:
  print(lst[l - 1])
else:
  if not flag:
    print(lst[l - 1])
  else:
    loop = len(lst) - loop_s
    n -= loop_s - 1
    c = n // loop
    r = n % loop
    ans = 0
    if c == 0:
      ans += lst[n + loop_s + 1]
    else:
      if r == 0:
        ans += lst[l - 1] + (c - 1) * (lst[l - 1] - lst[loop_s - 1])
      else:
        ans += lst[l - 1] + (c - 1) * (lst[l - 1] - lst[loop_s - 1]) + lst[loop_s + r - 1] - lst[loop_s - 1]
    print(ans)

Submission status: Runtime Error

Solution code:
N,X,M = map(int, open(0).read().split())
if N == 1:
    print(X)
else:
    A = []
    A.append(X)
    B = []
    for i in range(N-1):
        if pow(A[-1],2) < M:
            A.append(pow(A[-1],2))
        else:
            B.append(pow(A[-1],2,M))
            b = set(B)
            for i in range(N-1):
                temp = pow(B[-1],2,M)
                if temp not in b:
                    B.append(temp)
                    b.add(temp)
                else:
                    break
            else:
                continue
            break

if len(B) == 0:
    print(sum(A))
else:
    As = sum(A)
    Bs = sum(B)
    t1 = N - len(A)
    dm = divmod(t1,len(B))
    print(As+Bs*dm[0]+sum(B[:dm[1]]))

Submission status: Runtime Error

Solution code:
N,X,M = map(int, input().split())


A = [-1]*M
A[0] = X
i = 0
tmpans = 0
flag = False
check = [-1]*(M+1)
slice = -1
while i< N-1:
    newa = A[i]**2%M
    i+= 1
    if check[newa] != -1:
        flag = True
        slice = check[newa]
        break
    A[i] = newa
    check[newa] = i

if not flag:
    print(sum(A[:i+1]))

else:
    print(sum(A[:slice])+ sum(A[slice:i])*((N-slice)//(i-slice))+sum(A[slice:(N-slice)%(i-slice)]))

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.buffer.readline

n, x, mod = map(int, input().split())
ans = 0
temp = x
num = 1
# while temp < mod:
#     temp *= x
#     num += 1

# from kiriさん
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1:
            continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1:
                return 0
            t <<= 1
    return 1


def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)


def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k:
            ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1:
        ret[n] = 1
    if rhoFlg:
        ret = {x: ret[x] for x in sorted(ret)}
    return ret


A = [0] * (mod + 1)
jisho = primeFactor(mod)
if x * primeFactor(mod)[x] == mod:
    A[1] = x % mod
    ans += A[1]
    for i in range(2, num + 1):
        A[i] = A[i - 1] * A[i - 1] % mod
        ans += A[i]
        # print(ans)
    print(ans)
    exit()

kouho = {}
if n < mod:
    A[1] = x % mod
    ans += A[1]
    for i in range(2, n + 1):
        A[i] = A[i - 1] * A[i - 1] % mod
        ans += A[i]
        # print(ans)
else:
    A[1] = x
    ans += A[1]
    kouho[A[1]] = 1
    temp = A[1]
    for i in range(2, mod + 1):
        A[i] = temp * temp % mod
        if A[i] in kouho:
            migi = i
            break
        kouho[A[i]] = i
        temp = A[i]
    saisho = 0
    hidari = kouho[A[i]]
    saisho = sum(A[1:hidari])
    # for i in range(1, hidari):
    #     saisho += A[i]
    cycle_val = sum(A[hidari:migi])
    # cycle_val = 0
    # for i in range(hidari, migi):
    #     cycle_val += A[i]
    cycle = migi - hidari
    kaisu = n // cycle
    amari = n % cycle - (hidari - 1)
    amari %= cycle
    kaisu = (n - (amari + hidari - 1)) // cycle
    amari_val = sum(A[hidari : hidari + amari])
    # amari_val = 0
    # for i in range(hidari, hidari + amari):
    #     amari_val += A[i]
    ans = saisho + cycle_val * kaisu + amari_val
print(ans)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
l=[0]*m
s=[0]*m
t=p=0
while l[x]<1:
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
  t+=1
T=t-l[x]
S=s[p]+x-s[x]
if n<t:
  print(s[l.index(n-1)])
else:
  print(S*((n-l[x])//T)+s[l.index(l[x]+(n-l[x])%T-1)])

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
d = [-1] * (M + 1)
out = [0]
a = X
ans = 0
for i in range(1, N + 1):
    ans += a
    d[a] = i
    out.append(a)
    a = a ** 2 % M
    if d[a] != -1:
        loop_num = i + 1 - d[a]
        remain = N - i
        break
ans += sum(out[d[a]:d[a] + loop_num]) * (remain // loop_num)
ans += sum(out[d[a]:d[a] + (remain % loop_num)])

print(ans)

Submission status: Runtime Error

Solution code:
n,x,m = map(int,input().split())
ans= [0]*(n-1)
ans.append(x)
for i in range(n-1):
    ans[i] = x**2 % m
    x = ans[i]
print(str(sum(ans)))

Submission status: Runtime Error

Solution code:
N , X , M = map(int,input().split())
flag = [0]*M
S = X
SN = [0]*(M+1)
SN[1] = X 
A = X
loop = 1
flag[X%M] = 1
for i in range(N - 1):
  A = (A**2)%M
  if flag[A] == 0:
    flag[A] = loop
  else:
    loops = flag[A]
    break
  S += A
  SN[loop+1] = S
  loop += 1
if loop <N:
  ans = 0
  ans += SN[loops]
  dS = SN[loop] - SN[loops]
  dl = loop - loops
  ans += ((N-loops)//dl)*dS
  ans += SN[(N-loops)%dl+loops] - SN[loops]
  print(ans)
else:
  print(S)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,raw_input().split())
i=0
v=[x]
t={x:0}
p=0 
start=0
while True: 
    i+=1
    y=(x*x)%m 
    if y in t: 
        p+=(i-t[y]) 
        start+=t[y]
        break 
    p[y]=i
    v.append(y) 
    x=y 
ans=0
if n<(start): 
    for i in range(n): 
        ans+=v[i] 
    print ans 
else: 
    for i in range(start): 
        ans+=v[i] 
    n-=(start+1) 
    g=n%p 
    l=n/p 
    for i in range(start,n): 
        ans+=(l*v[i]) 
        if i<g: 
            ans+=v[i] 
print ans

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod = 998244353
INF = 10**18
eps = 10**-7

n,x,m = map(int,readline().split())

if n == 1:
    print(x)
    exit()

if n < 10**7:
    a = [0]*n
    a[0] = x
    for i in range(n-1):
        a[i+1] = a[i]**2%m
    print(sum(a))
    exit()

a = [0]*m
a[0] = x

for i in range(m-1):
    a[i+1] = a[i]**2%m

idx = [-1]*m

for i in range(m):
    if (idx[a[i]] == -1):
        idx[a[i]] = i
    else:
        idxx = idx[a[i]]
        now = i
        break

d = sum(a[idxx:now])
l = now-idxx
ans = sum(a[:idxx])
n -= idxx
ans += d*(n//l)
n = n%l
ans += sum(a[idxx:idxx+n])
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
it = lambda: list(map(int, input().strip().split()))


def solve():
    N, X, M = it()
    value = defaultdict(int)
    history = defaultdict(int)
    cur = 0
    cnt = 0
    for i in range(N):
        if X in history:
            break
        value[X] = cur
        history[X] = i
        cnt += 1
        cur += X
        X = X * X % M
    period = i - history[X]
    cur += (N - cnt) // period * (cur - value[X])
    for i in range((N - cnt) % period):
        cur += X
        X = X * X % M
    return cur

if __name__ == '__main__':
    print(solve())

Submission status: Runtime Error

Solution code:
n,x,m=inputintlist()
A=[x]
D=defaultdict(bool)
D[x]=True
kkey=None
for a in range(1,10**5+1000):
    num=(A[a-1]**2)%m
    if not D[num]:
        A.append(num)
        D[num]=True
    else:
        kkey=num
        break
if n<=10**5:
    print(sum(A[:n]))
else:
    i=A.index(kkey)
    nl=A[:i]
    l=A[i:]
    if n<=len(nl):
        print(sum(nl[:n]))
    else:
        ans=sum(nl)
        n-=len(nl)
        ans+=(n//len(l))*sum(l)
        n=n%len(l)
        ans+=sum(l[:n])
        print(ans)

Submission status: Runtime Error

Solution code:
n,X,m=map(int,input().split())
x=[0]*m
y=[0]*m
y[0]=X
z=[0]*(m+1)
z[X]+=1
for i in range(1,m):
    x[i]=(i**2)%m
for i in range(1,m+1):
    y[i]=x[y[i-1]]
    z[y[i]]+=1
    if z[y[i]]==2:
        e=i
        q=y[i]
        break
for i in range(len(y)):
    if y[i]==q:
        b=i
        break
l=y[b:e]
L=len(l)
s=sum(l)
#print(x)
#print(y)
#print(z)
#print(b,e)
#print(l)
#print(sum(y[:b]))
#print(((n-b)//L)*s)
#print(sum(l[:(n-b)%L]))
ans=sum(y[:b])+((n-b)//L)*s+sum(l[:(n-b)%L])
if n==1:
    print(X)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())

ans = [X]
a = X

for to in range(1, N):
    a = (a**2) % M
    if a in ans:
        break
    else:
        ans.append(a)
for fr, tmp in enumerate(ans, 0):
    if a == tmp:
        break
ret = 0

ret += sum(ans[:fr+1])
if fr != to:
    l = (N-fr)//(to-fr)
    ret += sum(ans[fr:to]) * l
    if N > fr + ((N-fr)//(to-fr))*(to-fr):
        l = N - (fr + ((N-fr)//(to-fr))*(to-fr))
        ret += sum(ans[fr:to][:l])

print(ret)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod = 998244353
INF = 10**18
eps = 10**-7

n,x,m = map(int,readline().split())

if n < 10**7:
    a = [0]*n
    a[0] = x
    for i in range(n-1):
        a[i+1] = a[i]**2%m
    print(sum(a))
    exit()

a = [0]*m
a[0] = x

for i in range(m-1):
    a[i+1] = a[i]**2%m

idx = [-1]*m

for i in range(m):
    if (idx[a[i]] == -1):
        idx[a[i]] = i
    else:
        idxx = idx[a[i]]
        now = i
        break

d = sum(a[idxx:now])
l = now-idxx
ans = sum(a[:idxx])
n -= idxx
ans += d*(n//l)
n = n%l
ans += sum(a[idxx:idxx+n])
print(ans)

Submission status: Runtime Error

Solution code:
N , X , M = map(int,input().split())
flag = [0]*M
S = X
SN = [0]*M
SN[1] = X 
A = X
loop = 1
flag[X%M] = 1
for i in range(N - 1):
  A = (A**2)%M
  if flag[A] == 0:
    flag[A] = loop
  else:
    loops = flag[A]
    break
  S += A
  SN[loop+1] = S
  loop += 1
if loop <N:
  ans = 0
  ans += SN[loops]
  dS = SN[loop] - SN[loops]
  dl = loop - loops
  ans += ((N-loops)//dl)*dS
  ans += SN[(N-loops)%dl+loops] - SN[loops]
  print(ans)
else:
  print(S)

Submission status: Runtime Error

Solution code:
N,X,M = map(int,input().split())

d = {X:0}
l = [X]

for i in range(1,N):
  l+=[(l[i-1]**2)%M]
  if l[i] in d:
    dl = l[d[l[i]]+1:]
    print(dl)
    l += dl*((N-i-1)//len(dl))
    if (N-i-1)%len(dl) != 0:
      l += dl[0:(N-i-1)%len(dl)]
    break
  d[l[i]] = i
print(l)
print(sum(l))

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.buffer.readline

n, x, mod = map(int, input().split())
ans = 0
temp = x
num = 1
# while temp < mod:
#     temp *= x
#     num += 1


A = [0] * (mod + 1)

# if temp == mod:
#     A[1] = x % mod
#     ans += A[1]
#     for i in range(2, num + 1):
#         A[i] = A[i - 1] * A[i - 1] % mod
#         ans += A[i]
#         # print(ans)
#     print(ans)
#     exit()

kouho = {}
if n < mod:
    A[1] = x % mod
    ans += A[1]
    for i in range(2, n + 1):
        A[i] = A[i - 1] * A[i - 1] % mod
        ans += A[i]
        # print(ans)
else:
    A[1] = x
    ans += A[1]
    kouho[A[1]] = 1
    temp = A[1]
    for i in range(2, mod + 1):
        A[i] = temp * temp % mod
        if A[i] in kouho:
            migi = i
            break
        kouho[A[i]] = i
        temp = A[i]
    saisho = 0
    hidari = kouho[A[i]]
    saisho = sum(A[1:hidari])
    # for i in range(1, hidari):
    #     saisho += A[i]
    cycle_val = sum(A[hidari:migi])
    # cycle_val = 0
    # for i in range(hidari, migi):
    #     cycle_val += A[i]

    cycle = migi - hidari
    kaisu = n // cycle
    amari = n % cycle - (hidari - 1)
    amari %= cycle
    kaisu = (n - (amari + hidari - 1)) // cycle
    amari_val = sum(A[hidari : hidari + amari])
    # amari_val = 0
    # for i in range(hidari, hidari + amari):
    #     amari_val += A[i]
    ans = saisho + cycle_val * kaisu + amari_val
print(ans)

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split())
count=x
now=x
flag=-1
sled=[now]
for i in range(1,n):
     now=(now*now)%m
     if now==0:
         flag=0
         break
     if now==1:
         flag==1
         nokori=n-i
         break
     if now in sled:
         start=sled.index(now)
         nokori=n-i
         flag=2
         break
     
     else:
         sled.append(now)
     count+=now
     #print(i,now,count)
sled=sled[start:]
if flag==1:
    count+=nokori
if flag==2:
    #print(count)
    roopnum=int(nokori/len(sled))
    amari=nokori%len(sled)
    
    one_roop=sum(sled)
    count+=one_roop*roopnum
    #print(count)
    for i in range(amari):
        count+=sled[i]
print(count)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
tmp=x
L=[x]
cnt_list=[0 for i in range(m+1)]
for i in range(n):
    tmp=tmp**2%m
    if tmp not in L:
        L.append(tmp)
        cnt_list[tmp]=i
    else:
        cnt=cnt_list[tmp]+1
        break
if len(L[cnt:])==0:
    ans=sum(L)+sum(L[cnt-1])*(n-len(L)+1)
else:
    times=(n-len(L[:cnt]))//len(L[cnt:])
    loss=(n-len(L[:cnt]))%len(L[cnt:])
    ans=sum(L[:cnt])+sum(L[cnt:])*times
    for i in range(loss):
          ans+=L[cnt:][i]
print(ans)

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split())

num_list = []
num2 = x

for i in range(n) :
    num1 = num2 % m
    if num1 in num_list :
        num = num_list.index(num1)
        break
    else :
        num_list.append(num1)
    num2 = num1 ** 2
    
acc1 = sum(num_list[:num])
acc2 = sum(num_list[num:])

num3 = n // len(num_list[num:])
num4 = n % len(num_list[num:])
print(acc1 + acc2 * num3 + sum(num_list[num : num4]))

Submission status: Runtime Error

Solution code:
n,x,m=map(int, input().split())
a = x
ans = a
l=[a]

for i in range(1,n):
    tmp=(a*a)%m
    a=tmp  
    ans+=tmp
    if a in l:
        lp = l.index(a)
        break
    else:
        l.append(a)

l2 = l[lp:]
tmp = sum(l2)

b=int((n-len(l))/len(l2))
c=(n-len(l))%len(l2)

ans+=b*tmp+sum(l2[:c])
print(ans)

Submission status: Runtime Error

Solution code:
N , X , M = map(int,input().split())
flag = [0]*M
S = X
SN = [0]*M
SN[1] = X 
A = X
loop = 1
flag[X%M] = 1
for i in range(N):
  A = (A**2)%M
  if flag[A] == 0:
    flag[A] = loop
  else:
    loops = flag[A]
    break
  S += A
  SN[loop+1] = S
  loop += 1
if loop <N:
  ans = 0
  ans += SN[loops]
  dS = SN[loop] - SN[loops]
  dl = loop - loops
  ans += ((N-loops)//dl)*dS
  ans += SN[(N-loops)%dl+loops] - SN[loops]
  print(ans)
else:
  print(SN[N])

Submission status: Runtime Error

Solution code:
N, X, M = map(int,input().split())

A = [X]
Asum = [X]
roopsum = 0
rooptimes = 0
ans = 0
index = 0
flag = 0

def f(x):
    global M
    global A
    global Asum
    if x == 1:
        return X
    else:
        A += [A[x-2]**2 % M]
        Asum += [Asum[x-2] + (A[x-2]**2 % M)]
        return A[x-2]**2 % M

for p in range(N):
    f(p+1)
    if A.count(A[p]) >= 2: #A[p] in A:
        index = A.index(A[p])
        roop = p - index
        roopsum += Asum[p-1] - Asum[index-1]
        """
        for q in range(index(A[p]),p):
            roopsum += A[q]
        """
        ans += Asum[index-1]
        rooptimes = (N-1-index)//(p - index)
        roopamari = (N-index)%(p - index)
        if A[p-1] == A[p]:
            rooptimes += 1
        ans += roopsum * rooptimes
        ans += Asum[index+roopamari-1] - Asum[index-1]
        flag = 1 #flag=1ならループがあった
        break
    
if flag == 0:
    ans += Asum[N-1]

print(ans)
print(index)
print(rooptimes)
print(roopamari)