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: Wrong Answer

Solution code:


def main():
    n, x, m = map(int, input().split())
    mflg = [0] + [-1] * (m-1)
    ltot = [x]

    tot = x
    a = x
    for i in range(1, n):
        a = a ** 2 % m
        if mflg[a-1] >= 0:
            z = (n - i) // (i - mflg[a-1]) - 1
            y = (n - i) % (i - mflg[a-1])
            tot += (ltot[mflg[a-1] - 1 + y] - ltot[mflg[a-1] - 1]) + (ltot[-1] - ltot[mflg[a-1] - 1]) * z
            break

        mflg[a-1] = i
        tot += a
        ltot.append(tot)

    print(tot)


main()

Submission status: Wrong Answer

Solution code:
n,x,m = map(int, input().split())
if m == 0:
    ans = 0
else:
    be = x % m
    ans = be
    memo = [[0,0] for i in range(m)]
    am = [be]
    memo[be-1] = [1,0]  #len-1
    for i in range(n-1):
        be = be**2 % m
        if be == 0:
            break
        elif memo[be-1][0] == 1:
            kazu = memo[be-1][1]
            l = len(am) -  kazu
            syou = (n-i) // l
            amari = (n-i)%l
            sum = 0
            for k in range(kazu, len(am)):
                sum += am[k]
            ans = ans + syou*sum
            if amari > 0:
                for j in range(kazu,kazu + amari -1):
                    ans += am[j]
            break
        else:
            ans += be
            am.append(be)
            memo[be-1][0] = 1
            memo[be-1][1] = len(am) -1
print(ans)

Submission status: Wrong Answer

Solution code:
N, X, M = [int(i) for i in input().split()]
ans = X
A = X
l = [X]
r = [X]

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

for i in range(1, N):
    A = A**2 % M
    if A == 0:
        break
    if A == 1:
        ans += N - i
        break
    if A in r:
        idx = r.index(A)
        if idx ==0:
            ans = (l[i - 1]) * ((N - idx) // (i - idx)) + \
                l[((N - idx) % (i - idx))]
        else:
            ans = (l[i - 1] - l[idx - 1]) * ((N - idx) // (i - idx)) + \
            l[((N - idx) % (i - idx)) + idx - 1]
        break
    ans += A
    r.append(A)
    l.append(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,X,M=map(int,input().split())
A = [X,]
alast=X
flag=False
for i in range(min(N,M)):
    P=alast**2%M
    if P in A:
        flag=True
        d = int(np.arange(len(A))[np.array(A)==P])
        C=A[d:]
        alast=P
        break
    else:
        A.append(P)
        alast=P
if alast==0:
    print(sum(C))
elif flag==False:
    suma=sum(A)
    res = (N)%len(A)
    print((N//len(A))*suma + sum(A[:res]))  
else:
    suma=sum(C)
    res = (N-d)%len(C)
    print(sum(A[:d])+((N-d)//len(C))*suma + sum(C[:res]))

Submission status: Wrong Answer

Solution code:
n, x, m = map(int,input().split())
lst = [0 for i in range(m)]
lst2 = [0, x]
i = 2
lst[x] = 1
c = 0
while True:
    if (i > n):
        break
    x = x**2%m
    if (lst[x] == 0):
        lst[x] = i
        lst2.append(lst2[i - 1] + x)
        i = i + 1
    else:
        lst2.append(lst2[i - 1] + x)
        c = 1
        break
if (c == 1):
    a = i - lst[x]
    b = lst2[i - 1] - lst2[i - 1 - a]
    i = i - 1
    c = (n - i)//a
    d = (n - i)%a
    ans = lst2[i - 1] + b*c + lst2[i - 1 - a + d] - lst2[i - 1 - a]
    print(ans)
else:
    print(lst2[n])

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
arr = [x]
for i in range(1, n+1):
    x = (x*x % m)
    if x in arr:
        break
    else:
        arr.append(x)
sa = sum(arr)
rem = n-i
argi = arr.index(x)
roop = arr[argi:]
nn, r = divmod(rem, len(roop))
print(sa + nn*sum(roop) + sum(roop[:r]))

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
A = X
P = set([A])
cnt, cnt2 = -1, -1
S = A
S2 = 0
off = -1
for i in range(N-1):
    A = A**2%M
    if A in P and cnt == -1:
        cnt = i
        off = A
    elif A ==off:
        cnt2 = i
        break
    S += A
    if cnt != -1:
        S2 += A
    P.add(A)
l = max(cnt2-cnt,1)
if cnt2==-1:
    res = S
else:
    res = 0
    print(l, S, S2, cnt, cnt2)
    for i in range((N-cnt-1)%l):
        res += off
        off = off**2%M
    res += S + ((N-cnt2-1)//l)*S2
print(res)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, X, M = map(int, input().split())

mod_check_list = [False for _ in range(M)]
mod_list = [(X ** 2) % M]
counter = 1
mod_sum = (X ** 2) % M
last_mod = 0
for i in range(M):
    now_mod = (mod_list[-1] ** 2) % M
    if mod_check_list[now_mod]:
        last_mod = now_mod
        break
    mod_check_list[now_mod] = True
    mod_list.append(now_mod)
    counter += 1
    mod_sum += now_mod

loop_start_idx = 0
for i in range(counter):
    if last_mod == mod_list[i]:
        loop_start_idx = i
        break

loop_list = mod_list[loop_start_idx:]
loop_num = counter - loop_start_idx
ans = 0
if mod_list[-1] == 0:
    ans = X + sum(mod_list[:min(counter, N - 1)])
else:
    if (N - 1) <= counter:
        ans = X + sum(mod_list[:counter])
    else:
        ans += X + mod_sum
        N -= (counter + 1)
        ans += sum(loop_list) * (N // loop_num) + sum(loop_list[:N % loop_num])
print(ans)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
amr = []
for i in range(n):
    if i == 0:
        x %= m
        amr.append(x)
        continue
    x = pow(x, 2, m)

    if x in amr:
        print('----', i)
        break
    if x == 0:
        break
    amr.append(x)

if x == 0:
    print(sum(amr[:n]))
else:
    idx = amr.index(x)

    loop = sum(amr[idx:])
    l = len(amr[idx:])

    if n >= idx:
        cnt = (n-idx)//l
        print(cnt*loop + sum(amr[:idx]) + sum(amr[idx:idx+n-idx-cnt*l:]))
    else:
        print(sum(amr[:n]))

Submission status: Wrong Answer

Solution code:
n, x, m = map(int,input().split())
f = []
y = x
while(True):
  y = y**2%m
  if y in f:
    break
  f.append(y)
ind = f.index(y)
if n-1 <= len(f):
  print(x + sum(f[:n-1]))
else:
  loop = len(f)-ind
  p = (n-1)//loop
  q = (n-1)%loop
  print(x + sum(f[:ind])+sum(f[ind:])*p + sum(f[ind:ind+q-1]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, X, M = map(int, input().split())
A = [X]
visited = set()
visited.add(X)

idx = defaultdict()
idx[X] = 0

iii = -1

for i in range(1, M):
    tmp = (A[-1]**2) % M
    if tmp not in visited:
        A.append(tmp)
        visited.add(tmp)
        idx[tmp] = i
    else:
        iii = idx[tmp]

print(A)
print(len(A))
print(iii)

ans = 0

ans += sum(A[:iii])
N -= iii

l = len(A) - iii

ans += (N // l) * sum(A[iii:])
N -= N // l * l

ans += sum(A[iii:iii + N])

print(ans)
exit()

if A[-1] == 0:
    print(sum(A))
    exit()
else:
    l = len(A)
    ans = 0
    if N % l == 0:
        ans += sum(A) * (N // l)
    else:
        ans += sum(A) * (N // l)
        rest = N % l
        if iii == -1:
            ans += sum(A[:rest])
        else:
            ans += sum(A[i:iii + rest])
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

ans = x

i = 0
a_list = [x]
a = x
flag = 0
while(i<n):
    i+=1
    a = (a*a) % m
    if a in a_list:
        flag = 1
        break
    a_list.append(a)
    ans += a
    
if flag == 1:
    b = a_list.index(a)
    tmp_sum = 0
    for j in range(b,len(a_list)):
        tmp_sum += a_list[j]
    blen = len(a_list)-b
    ans += tmp_sum*((n-i)//blen)
    for k in range((n-i) % blen):
        ans += a_list[i+k-blen]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N,X,M = I()
ans = [X]
pt = 0
F1 = 0
F2 = 0
for i in range(N):
    X = pow(X,2,M)
    if X == 0:
        pt = i
        F1 = 1
        break
    if X == 1:
        pt = i
        F2 = 1
        break
    if X in ans:
        pt = i
        break
    ans.append(X)
if F1 == 1:
    print(sum(ans))
elif F2 == 1:
    print(sum(ans)+N-pt-1)
elif pt == 0:
    print(sum(ans[:N]))
else:
    i = ans.index(X)
    num = pt-i+1
    m = (N-i)%num
    c = (N-i)//num
    print(sum(ans[:i])+sum(ans[i:i+m])+sum(ans[i:])*c)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int,input().split())
f = []
y = x
while(True):
  y = y**2%m
  if y in f:
    break
  f.append(y)
ind = f.index(y)
print(f)
if n-1 <= len(f):
  print(x + sum(f[:n-1]))
else:
  loop = len(f)-ind
  p = (n-1)//loop
  q = (n-1)%loop
  print(f[ind:ind+q-1],p)
  print(x + sum(f[:ind])+sum(f[ind:])*p + sum(f[ind:ind+q-1]))

Submission status: Wrong Answer

Solution code:
import numpy as np
n, x, m = list(map(int,input().split()))

def find_num(result,num:int) -> int:
    tmp=result.index(num)
    tmp_e=len(result)-tmp
    tmp_a=result[tmp:]
    
    times = (n-tmp)//len(tmp_a)
    add_len = (n-tmp)%len(tmp_a)
    add_list = sum(tmp_a)*times
    if add_len==0:
        return int(sum(result[:tmp]+add_list))
    else:
        return int(sum(result[:tmp]+tmp_a[:add_len])+add_list)

tmp_k=np.arange((m))**2
tmp_v=tmp_k%m

tmp=x
result=[tmp]
tmp_list=[0]*(m)
for i in range(n-1):
    tmp=tmp_v[tmp]
    if tmp_list[tmp] == 1:
        print(find_num(result,tmp))
        break
    result.append(tmp)
    tmp_list[tmp]=1
else:
    print(sum(result))

Submission status: Wrong Answer

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

num_list = []
num2 = x
num = -1
for i in range(n) :
    try :
        num1 = num2 % m
        if num1 in num_list :
            num = num_list.index(num1)
            break
        else :
            num_list.append(num1)
        num2 = num1 ** 2
    except ZeroDivisionError :
        break

if num_list == [] :
    print(0)
elif num == -1 :
    print(sum(num_list))
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: Wrong Answer

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

Submission status: Wrong Answer

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

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

if lp != 0:
    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])-l2[0]
 
print(ans)

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
# 一定回数を経ると循環するので最後にかければよい
a_i = x
log = [x]
app=[-1]*m
app[x]=0
last = x
for i in range(1,n):
  a_i = (a_i**2)%m
  if app[a_i] > -1:
    last = a_i
    break
  app[a_i] = i
  log.append(a_i)

# ループの手前(or最後)まで足し合わせる
ans = sum(log[:min(n, app[last])])
if n > app[last]:
  # ループ中合計
  ans += sum(log[app[last]:]) * ((n-app[last]) // (len(log) - app[last]))
  # 末端合計
  ans += sum(log[app[last]:app[last] + (n-app[last]) % (len(log) - app[last])])
print(ans)
print(*log)

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input('').split(' '))
print((int((n*(n+1)*(2*n+1))/6)-int((x*(x-1)*(2*x-1))/6))%m)

Submission status: Wrong Answer

Solution code:
N, X, M = [int(i) for i in input().split()]
ans = X
A = X
l = [X]
r = [X]

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

for i in range(1, N):
    A = A**2 % M
    if A == 0:
        break
    if A == 1:
        ans += N - i
        break
    if A in r:
        idx = r.index(A)
        ans = (l[i - 1] - l[idx - 1]) * ((N - idx) // (i - idx)) + \
            l[((N - idx) % (i - idx)) + idx - 1]
        break
    ans += A
    r.append(A)
    l.append(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N, X, M = [int(i) for i in input().split()]
ans = X
A = X
l = [X]
r = [X]

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

for i in range(1, N):
    A = A**2 % M
    if A == 0:
        break
    if A == 1:
        ans += N - i
        break
    if A in r:
        idx = r.index(A)
        ans = (l[i - 1] - l[idx - 1]) * ((N - idx) // (i - idx)) + \
            l[((N - idx) % (i - idx)) + idx - 1]
        break
    ans += A
    r.append(A)
    l.append(ans)
print(ans)

(2+4+16+256+431)+(324+359+18)*331+(324+359)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

ans = 0

aa = x
ans += aa
aset = set([aa])
alist = [aa]

for i in range(1,n):
    aa = pow(aa,2,m)
    if aa in aset:
        ind = alist.index(aa)
        loop = alist[ind:i]
        nloop = (n-i+1)//len(loop)+1
        ans += sum(loop)*(nloop-1)
        ans += sum(loop[0:(n-i+1)%len(loop)-1])
        break
    else:
        ans += aa
        aset.add(aa)
        alist.append(aa)

    if aa == 0:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n,x,m = map(int, input().split())
be = x % m
ans = be
memo = [[0,0] for i in range(m)]
am = [be]
memo[be-1] = [1,0]  #len-1
for i in range(n-1):
    be = be**2 % m
    if be == 0:
        break
    elif memo[be-1][0] == 1:
        kazu = memo[be-1][1]
        l = len(am) -  kazu
        syou = (n-i) // l
        amari = (n-i)%l
        sum = 0
        for k in range(kazu, len(am)):
            sum += am[k]
        ans = ans + syou*sum
        if amari > 0:
          for j in range(kazu,kazu + amari -1):
            ans += am[j]
        break
    else:
        ans += be
        am.append(be)
        memo[be-1][0] = 1
        memo[be-1][1] = len(am) -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N,X,M = I()
ans = [X]
pt = 0
F1 = 0
F2 = 0
if M == 1:
    print(X)
    exit()
for i in range(N):
    X = pow(X,2,M)
    if X == 0:
        pt = i
        F1 = 1
        break
    if X == 1:
        pt = i
        F2 = 1
        break
    if X in ans:
        pt = i
        break
    ans.append(X)
if F1 == 1:
    print(sum(ans))
elif F2 == 1:
    print(sum(ans)+N-pt-1)
elif pt == 0:
    print(sum(ans))
else:
    i = ans.index(X)
    num = pt-i+1
    m = (N-i)%num
    c = (N-i)//num
    print(sum(ans[:i])+sum(ans[i:i+m])+sum(ans[i:])*c)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, x, m = list(map(int,input().split()))

def find_num(result,num:int) -> int:
    tmp=result.index(num)
    tmp_e=len(result)-tmp
    tmp_a=result[tmp:]
    
    times = (n-tmp)//len(tmp_a)
    add_len = (n-tmp)%len(tmp_a)
    add_list = sum(tmp_a)*times
    if add_len==0:
        return sum(result[:tmp]+add_list)
    else:
        return int(sum(result[:tmp]+tmp_a[:add_len])+add_list)

tmp_k=np.arange((m))**2
tmp_v=tmp_k%m

tmp=x
result=[tmp]
tmp_list=[0]*(10**5)
for i in range(n-1):
    tmp=tmp_v[tmp]
    if tmp_list[tmp] == 1:
        print(find_num(result,tmp))
        break
    result.append(tmp)
    tmp_list[tmp]=1
else:
    print(sum(result))

Submission status: Wrong Answer

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

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

if lp != 0:
    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])-l2[0]
 
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N,X,M=[int(s) for s in input().split()]

MAX=M+1
sq_max=int(math.sqrt(MAX))

seive=[1 for _ in range(MAX+1)]
seive[0]=0
seive[1]=0
for i in range(sq_max+1):
  if seive[i]==0:
    continue
  for j in range(i*2,MAX+1,i):
    seive[j]=0

def factor(num):
  factordic={}
  for i in range(2,min([MAX+1,int(math.sqrt(num))+1])):
    if seive[i]==1 and num%i==0:
      factordic[i]=1
      num//=i
      while num%i==0:
        factordic[i]+=1
        num//=i
    if num==1:
      break
  else:
    factordic[num]=1
  return(factordic)

Mdic=factor(M)

#M=G*M2にわける（GはMとXの最大公約数）
#M2の約数の個数を取得
G=1
divM2=1
for v,k in Mdic.items():
  if X%v==0:
    G*=(v**k)
  else:
    divM2*=((v-1)*(v**(k-1)))

#divM2の奇数部分の約数の個数を取得する
divM2dic=factor(divM2)
divdivM2=1
for v,k in divM2dic.items():
  if v==2:
    continue
  else:
    divdivM2*=((v-1)*(v**(k-1)))


#Mで割った余りを取得する
modls=[0 for _ in range(divdivM2+35)]
modls[0]=X
for i in range(1,divdivM2+35):
  modls[i]=(modls[i-1]**2)%M


ans=0
#初項から第34項まで足す
a=[0 for _ in range(34)]
a[0]=X
for i in range(1,min([N,34])):
  a[i]=(a[i-1]**2)%M
ans+=sum(a)

if N>34:
  if divM2>1:
  #第35項から先は、modGで0になっているはず
  #divdivM2個ごとにループ
    modls2=modls[34:]
    modls3=modls2[:divdivM2]
    total=sum(modls3)
    ans+=((N-34)//divdivM2)*total*G
    ans+=sum(modls3[:((N-34)%divdivM2)+1])*G

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,X,M=map(int,input().split())
A = [X,]
alast=X
flag=False
for i in range(M):
    P=alast**2%M
    if P in A:
        flag=True
        d = int(np.arange(len(A))[np.array(A)==P])
        C=A[d:]
        alast=P
        break
    else:
        A.append(P)
        alast=P
if alast==0:
    print(sum(C))
elif flag==False:
    suma=sum(A)
    res = (N)%len(A)
    print(((N)//len(A))*suma + sum(A[:res]))  
else:
    suma=sum(C)
    res = (N-d)%len(C)
    print(sum(A[:d])+((N-d)//len(C))*suma + sum(C[:res]))

Submission status: Wrong Answer

Solution code:
n,x,m = map(int, input().split())
be = x % m
ans = be
memo = [[0,0] for i in range(m)]
am = [be]
memo[be-1] = [1,0]  #len-1
for i in range(n-1):
    be = be**2 % m
    if be == 0:
        break
    elif memo[be-1][0] == 1:
        kazu = memo[be-1][1]
        l = len(am) -  kazu
        syou = (n-i) // l
        amari = (n-i)%l
        sum = 0
        for k in range(kazu, len(am)):
            sum += am[k]
        ans = ans + syou*sum
        if amari > 0:
            if amari == 1:
                ans += am[kazu]
            else:
                for j in range(kazu,kazu + amari -1):
                    ans += am[j]
        break
    else:
        ans += be
        am.append(be)
        memo[be-1][0] = 1
        memo[be-1][1] = len(am) -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N,X,M = I()
ans = [X]
pt = 0
F1 = 0
F2 = 0
for i in range(N):
    X = pow(X,2,M)
    if X == 0:
        pt = i
        F1 = 1
        break
    if X == 1:
        pt = i
        F2 = 1
        break
    if X in ans:
        pt = i
        break
    ans.append(X)
if F1 == 1:
    print(sum(ans))
elif F2 == 1:
    print(sum(ans)+N-pt-1)
elif pt == 0:
    print(sum(ans))
else:
    i = ans.index(X)
    num = pt-i+1
    m = (N-i)%num
    c = (N-i)//num
    print(sum(ans[:i])+sum(ans[i:i+m])+sum(ans[i:])*c)

Submission status: Wrong Answer

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 
    t[y]=i
    v.append(y) 
    x=y 
ans=0 

if n<(len(v)): 
    for i in range(n): 
        ans+=v[i] 
    print ans 
else: 
    for i in range(start): 
        ans+=v[i] 
    n-=(start) 
    g=n%p 
    l=n//p 
    for i in range(start,len(v)): 
        ans+=(l*v[i]) 
        if i<g: 
            ans+=v[i] 
    print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, X, M = map(int, input().split())

mod_check_list = [False for _ in range(M)]
mod_list = [(X ** 2) % M]
counter = 1
mod_sum = (X ** 2) % M
last_mod = 0
for i in range(M):
    now_mod = (mod_list[-1] ** 2) % M
    if mod_check_list[now_mod]:
        last_mod = now_mod
        break
    mod_check_list[now_mod] = True
    mod_list.append(now_mod)
    counter += 1
    mod_sum += now_mod

loop_start_idx = 0
for i in range(counter):
    if last_mod == mod_list[i]:
        loop_start_idx = i
        break

loop_list = mod_list[loop_start_idx:]
loop_num = counter - loop_start_idx
ans = 0
if mod_list[-1] == 0:
    ans = X + mod_sum
else:
    if (N - 1) <= counter:
        ans = X + sum(mod_list[:counter])
    else:
        ans += X + mod_sum
        N -= (counter + 1)
        ans += sum(loop_list) * (N // loop_num) + sum(loop_list[:N % loop_num])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N,X,M = I()
ans = [X]
pt = 0
F1 = 0
F2 = 0
for i in range(N):
    X = pow(X,2,M)
    if X == 0:
        pt = i
        F1 = 1
        break
    if X == 1:
        pt = i
        F2 = 1
        break
    if X in ans:
        pt = i
        break
    ans.append(X)
    print(X)
if F1 == 1:
    print(sum(ans))
elif F2 == 1:
    print(sum(ans)+N-pt-1)
elif pt == 0:
    print(sum(ans))
else:
    i = ans.index(X)
    num = pt-i+1
    m = (N-i)%num
    c = (N-i)//num
    print(sum(ans[:i])+sum(ans[i:i+m])+sum(ans[i:])*c)

Submission status: Wrong Answer

Solution code:
import math

n, x, m = map(int, input().split())
ans = x % n
over_m = False
is_loop = False
loop_lis = [-100]
loop_num = 0
for i in range(2, n + 1):
    tmp = pow(x, 2) % int(m)
    if loop_lis[0] == tmp:
        remain = (n - i + 1) % len(loop_lis)
        loop_num = math.floor((n - i + 1) / len(loop_lis))
        if remain == 0:
            ans += loop_num * loop_lis[-1]
        else:
            ans += loop_num * loop_lis[-1] + loop_lis[remain - 1]
        break
    else:
        ans += tmp
    if is_loop:
        loop_lis.append(tmp + loop_lis[-1])
    if not over_m:
        if pow(x, 2) >= m:
            loop_lis = [tmp]
            over_m = True
            is_loop = True
    x = tmp
print(ans)

Submission status: Wrong Answer

Solution code:
N, X, M = [int(x) for x in input().split()]
copy = M

k = 0
while M % 2 == 0:
    k += 1
    M = M // 2
L = M

order = 1
if L != 1:
    e = 2 % L
    while e != 1:
        order += 1
        e = (2 * e) % L

A = [0] * (k + order + 1)
A[1] = X
for i in range(2, k + order + 1):
    A[i] = (A[i - 1] * A[i - 1]) % copy

S = sum(A[k + 1:])
ans = 0
if N <= k:
    ans = sum(A[1:N + 1])
else:
    q, r = (N - k) // order, (N - k) % order
    ans = sum(A[1:k + 1]) + S * q + sum(A[k + 1:k + r + 1])

print(ans)

Submission status: Wrong Answer

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

res = X
remainder_list = set([X % M])
remainder_loop = []

a_part = []

flg = False

a = X

for i in range(N - 1):
    a = a ** 2 % M
    if a in remainder_list:
        res_loop = 0
        rem_trig = a
        cnt = 0
        a_part.append(a)
        a_tmp = a
        while True:
            remainder_loop.append(a)
            res_loop += a
            a = a ** 2 % M
            a_part.append(a_part[-1] + a)
            cnt += 1
            if a == rem_trig or cnt + i >= N + 1:
                break
        res += ((N - i) // cnt) * res_loop + a_part[(N - i - 2) % cnt]
        break
    else:
        remainder_list.add(a)
        res += a

print(res)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int,input().split())
lst = [0 for i in range(m)]
lst2 = [x]
i = 2
lst[x] = 1
while True:
    if (i > n):
        break
    x = x**2%m
    if (lst[x] == 0):
        lst[x] = i
        lst2.append(lst2[i - 2] + x)
        i = i + 1
    else:
        break
a = i - lst[x]
b = lst2[i - 2] - lst2[i - 2 - a]
i = i - 1
c = (n - i)//a
d = (n - i)%a
ans = lst2[i - 1] + b*c + lst2[i - 1 - a + d] - lst2[i - 1 - a]
print(ans)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
# init = x
# 二乗してあまりが x となる個数
amari = [0] * (m + 1)
for i in range(m + 1):
    y = pow(i, 2, m)
    amari[y] += 1 

visited = [0] * (m + 1)
now = x
loop = 1
while True:
    y = pow(now, 2, m)
    if visited[y] == 1:
        last = y
        break
    visited[y] += 1
    now = pow(now, 2, m)
    loop += 1

# print(visited)
# print(loop)
# print(last, 'last')

res = x

# 循環する手前まで
cnt_init = 1
now = x
while True:
    y = pow(now, 2, m)
    # print(y)
    if y == last:
        break
    res += pow(now, 2, m)
    now = pow(now, 2, m)
    cnt_init += 1

print(loop)
loop = loop - cnt_init
print(cnt_init)
print(loop)

# 循環
cnt = (n - cnt_init) // loop
tmp = last # 最初足し込む
now = last
while True:
    y = pow(now, 2, m)
    if y == last:
        break
    tmp += pow(now, 2, m)
    # print('y', y)
    now = pow(now, 2, m)

res += tmp * cnt

# 残り
nokori = (n - cnt_init) % loop

if nokori == 0:
    print(res)
    exit()

now = last
res += last
for _ in range(nokori-1):
    res += pow(now, 2, m)
    now = pow(now, 2, m)

print(res)

Submission status: Wrong Answer

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,input().split())
s=set()
l=[]
flag=False
cnt=1
ans=0

l.append(x)
for i in range(m):
  if x not in s:
    s.add(x)
    x=(x**2)%m
    l.append(x)
  else:
    break

h=len(l)
cnt=1
num=0
for i in range(h):
  if l[i]==l[h-1]:
    while l[i+cnt]!=l[h-1]:
      cnt+=1
    flag=True
    break
  else:
    num+=1
    ans+=l[i]

n-=num
if num!=0:
  del l[h-1]
  del l[0:num]

if n>=len(l):
  mod=n%len(l)
  ans+=sum(l)*(n//len(l))
  for i in range(1,mod):
    ans+=l[i-1]
  print(ans)
else:
  for i in range(n):
    ans+=l[i]
  print(ans)

Submission status: Wrong Answer

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

s=set()

while True:
    if X==0:
        print(sum(s))
        exit()
    if X in s:
        break
    else:
        s.add(X)
        X=X**2%M
    

L=len(s)

ans=N//len(s)*sum(s)
r=N%len(s)

for _ in range(r):
    ans+=_X
    _X=_X**2%M
print(ans)

Submission status: Wrong Answer

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

a = [x]
b = [x]
rabbit = x
turtle = x
flag = False

start = 0
end = 1

while True:
  rabbit = (rabbit ** 2) % m
  rabbit = (rabbit ** 2) % m
  turtle = (turtle ** 2) % m
  a.append(turtle)
  b.append(b[-1] + turtle)
  
  if rabbit == turtle:
    break

if len(a) >= n:
  print(b[n - 1])
elif rabbit == 0:
  print(b[-1])
else:
  rabbit = x
  while rabbit != turtle:
    rabbit = (rabbit ** 2) % m
    turtle = (turtle ** 2) % m
    start += 1
    a.append(turtle)
    b.append(b[-1] + turtle)

  turtle = (turtle ** 2) % m
  end = start + 1
  a.append(turtle)
  b.append(b[-1] + turtle)
  while rabbit != turtle:
    turtle = (turtle ** 2) % m
    end += 1
    a.append(turtle)
    b.append(b[-1] + turtle)

  if len(a) >= n:
    print(b[n - 1])
  elif a[-1] == 0:
    print(b[-1])
  else:
    ans = b[start - 1]
    ans += (b[end - 1] - b[start - 1]) * ((n - start) // (end - start))
    if (n - start) % (end - start) != 0:
      ans += b[((n - start) % (end - start)) + start - 1] - b[start - 1]
    print(ans)

Submission status: Wrong Answer

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

res = X
remainder_list = set([X % M])
remainder_loop = []

a_part = []

flg = False

a = X

for i in range(N - 1):
    a = a ** 2 % M
    if a in remainder_list:
        res_loop = 0
        rem_trig = a
        cnt = 0
        a_part.append(a)
        a_tmp = a
        while True:
            remainder_loop.append(a)
            res_loop += a
            a = a ** 2 % M
            a_part.append(a_part[-1] + a)
            cnt += 1
            if a == rem_trig or cnt + i >= N:
                break
        res += ((N - i) // cnt) * res_loop + a_part[(N - i - 2) % cnt]
        break
    else:
        remainder_list.add(a)
        res += a

print(res)

Submission status: Wrong Answer

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:-1]) + 1

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

rest_mo = sum(list_mo[1: rest_+1]) 

result = initial + plus_mo + rest_mo

print(result)

Submission status: Wrong Answer

Solution code:
import math

n, x, m = map(int, input().split())
ans = x % n
over_m = False
is_loop = False
loop_lis = [-100]
loop_num = 0
for i in range(2, n + 1):
    tmp = pow(x, 2) % int(m)

    if loop_lis[0] == tmp:
        remain = (n - i + 1) % len(loop_lis)
        loop_num = math.floor((n - i + 1) / len(loop_lis))
        ans += loop_num * sum(loop_lis) + sum(loop_lis[:remain])
        break
    else:
        ans += tmp
    if is_loop:
        loop_lis.append(tmp)
    if not over_m:
        if pow(x, 2) >= m:
            loop_lis = [tmp]
            over_m = True
            is_loop = True
    x = tmp
print(ans)

Submission status: Wrong Answer

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