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, mod = map(int, input().split())
    if(x==1):
        print(n)
        return
    if(x==0):
        print(0)
        return
    ans=0
    las=[0]*(mod+10)
    sum=[0]*(mod+10)
    s=0
    for i in range(1,n+1):
        las[x]=i
        ans+=x
        s+=x
        sum[i]=sum[i-1]+x
        x*=x
        x%=mod
        if(las[x]>=1):
            lo=i-las[x]+1
            assert lo>=1
            s-=sum[las[x]-1]
            assert s>=0
            re=n-i
            assert re>=0
            ans+=(int)(re/lo)*s
            re%=lo
            while re>0:
                re-=1
                ans+=x
                x*=x
                x%=mod
            print(ans)
            return
main()

Submission status: Wrong Answer

Solution code:
def main():
    n, x, mod = map(int, input().split())
    if(x==1):
        print(n)
        return
    if(x==0):
        print(0)
        return
    ans=0
    las=[0]*mod
    sum=[0]*(mod+10)
    s=0
    for i in range(1,n+1):
        las[x]=i
        ans+=x
        s+=x
        sum[i]=sum[i-1]+x
        x*=x
        x%=mod
        if(las[x]>=1):
            lo=i-las[x]+1
            s-=sum[las[x]-1]
            re=n-i
            ans+=(int)(re/lo)*s
            re%=lo
            while re>0:
                re-=1
                ans+=x
                x*=x
                x%=mod
            print(ans)
            return
main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import queue
import collections
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []


def main():
	N,X,M=i_map()

	Y = X

	went_array = []
	for i in range(0,M):
		went_array.append(-1)

	loop_flag = False
	first = -1
	second = -1
	value = -1
	for i in range(0,N):

		if(went_array[Y] != -1):
			loop_flag = True
			first = went_array[Y]
			second = i
			value = Y
			break

		went_array[Y] = i
		Y = (Y*Y) % M

	if(loop_flag == False):
		Z = X
		sum = 0

		for i in range(0,N):
			sum += Z
			Z = (Z*Z)%M

		print(sum)

	else:
		Z = X
		sum1 = 0
		for i in range(0,first):
			sum1 += Z
			Z = (Z*Z)%M

		Z = value
		cum = []
		cum.append(Z)
		Z = (Z*Z) %M
		for i in range(1,second-first):
			cum.append(cum[i-1]+Z)
			Z = (Z*Z) %M

		sum2 = ((N-first)//(second-first))*cum[second-first-1]


		sum3 = cum[((N-1-first)%(second-first))]

		print(sum1+sum2+sum3)

	return

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import queue
import collections
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []


def main():
	N,X,M=i_map()

	Y = X

	went_array = []
	for i in range(0,M):
		went_array.append(-1)

	loop_flag = False
	first = -1
	second = -1
	value = -1
	for i in range(0,min(M,N)):

		if(went_array[Y] != -1):
			loop_flag = True
			first = went_array[Y]
			second = i
			value = Y
			break

		went_array[Y] = i
		Y = (Y*Y) % M

	if(loop_flag == False):
		Z = X
		sum = 0

		for i in range(0,N):
			sum += Z
			Z = (Z*Z)%M

		print(sum)

	else:
		Z = X
		sum1 = 0
		for i in range(0,first):
			sum1 += Z
			Z = (Z*Z)%M

		Z = value
		cum = []
		cum.append(Z)
		Z = (Z*Z) %M
		for i in range(1,second-first):
			cum.append(cum[i-1]+Z)
			Z = (Z*Z) %M

		sum2 = ((N-first)//(second-first))*cum[second-first-1]


		sum3 = cum[((N-1-first)%(second-first))]

		print(sum1+sum2+sum3)

	return

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:

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

res = X
a = X
cnt = 0
for i in range(N - 1):
    a = pow(a, 2, M)
    res += a
    if a == X:
        cnt = i + 1
        break

if cnt > 0:
    res *= (N // cnt)
    for i in range(N % cnt):
        a = pow(a, 2, M)
        res += a

print(res)

Submission status: Wrong Answer

Solution code:
N, X, M = (int(i) for i in input().split())
res0 = X
res1 = 0
res2 = 0
stage = 0
rang = 0
q = 0
hist = set()
for i in range(1, N):
    X = X*X%M
    if X in hist:
        stage += 1
        rang = (i - rang)
        hist.clear()
    if stage == 0:
        res0 += X
    elif stage == 1:
        res1 += X
    else:
        q, mod = divmod((N-i), rang)
        res2 = X
        for j in range(mod-1):
            X = X*X%M
            res2 += X
        break
    hist.add(X)
    X = X
print(res0+res1*(q+1)+res2)

Submission status: Wrong Answer

Solution code:
# input:6 3 7
# A=[3,2,4,2,4,2]
# l,r=2,4
# output:3+2+4+2+4+2=17

N,X,M=map(int,input().split())
lis=[0]*M
a=X
lis[a]=1

mod=[0]*(min(N-1,M)+2)
mod[1]=a

A=[0]*(min(N-1,M)+2)
A[1]=a

if N==1:
    print(a)
else:
    
    for i in range(2,min(N-1,M)+2):
        a=a**2%M
        #print(a)
        
        if a==0:
            print(A[i-1])
            break
        elif lis[a]!=0:
            l,r=mod[a],i
            #print(l,r)
            q,m=divmod(N-l+1,r-l)
            #print(q,m)
            #print(A)
            print(A[l-1] + q*(A[r-1]-A[l-1]) + (A[l+m-1]-A[l-1]))
            break
        else:
            mod[i]+=a
            lis[a]+=1
            A[i]=A[i-1]+a
            
    else:
        print(A[i])

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, X, M = LI()
    A = [X]
    seen = set()
    seen.add(X)
    while True:
        an = A[-1]
        an1 = ((an % M) * (an % M)) % M
        if an1 in seen:
            break
        else:
            A.append(an1)
            seen.add(an1)
    start_loop_i = 0
    for i, a in enumerate(A):
        if an1 == a:
            start_loop_i = i
            break
    loop_len = len(A) - start_loop_i
    loop_sum = sum(A[start_loop_i:])

    end = False
    ans = 0
    for i in range(start_loop_i):
        N -= 1
        ans += A[i]
        if N == 0:
            end = True
            break
    if end:
        print(ans)

    ans += loop_sum * (N // loop_len)
    
    if N % loop_len > 0:
        N %= loop_len
        for i in range(N):
            ans += A[start_loop_i + i]
    print(ans)






main()

Submission status: Wrong Answer

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

f=1
w=[]
d=[0]*(m+2)
t=[0]
chk=n
for i in range(m+1):
    f=pow(2,i)
    p=pow(x,f,m)
    if d[p]: break
    d[p]=1
    #w.append(p)
    #t.append(t[-1]+p)
    #f*=2
    chk-=1
    if chk==0:
        print(t[-1])
        exit()
print(-1)
exit()

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
if x==0:
  print(0)
elif x==1:
  print(1)
else:
  l=[0 for i in range(m)]
  a=[]
  now=x
  nex=0
  ans=x
  cnt=1

  while(now<m and cnt<n):
    nex=pow(now,2)
    if nex<m:
      ans+=nex
      now=nex
      cnt+=1
    else:

      nex=nex%m
      a.append(nex)
      l[nex-1]=1
      break

  if cnt<n:
    while(l[nex]<=1):
      now=pow(nex,2,m)
      nex=now
      if l[nex-1]==1:
        break
      else:
        l[now-1]+=1
        a.append(now)
    al=sum(l)
    amari=(n-cnt)%al
    ko=(n-cnt)//al
    ans+=ko*sum(a)+sum(a[:amari])
    print(ans)
  else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
if x==0:
  print(0)
elif x==1:
  print(1)
else:
  l=[0 for i in range(m)]
  a=[]
  now=x
  nex=0
  ans=x
  cnt=1

  while(now<m and cnt<n):
    nex=pow(now,2)
    if nex<m:
      ans+=nex
      now=nex
      cnt+=1
    else:

      nex=nex%m
      a.append(nex)
      l[nex-1]=1
      break


  while(l[nex]<=1):
    now=pow(nex,2,m)
    nex=now
    if l[nex-1]==1:
      break
    else:
      l[now-1]+=1
      a.append(now)
  al=sum(l)
  amari=(n-cnt)%al
  ko=(n-cnt)//al
  ans+=ko*sum(a)+sum(a[:amari])
  print(ans)

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
if x==0:
  print(0)
elif x==1:
  print(1)
else:
  l=[0 for i in range(m)]
  a=[]
  now=x
  nex=0
  ans=x
  cnt=1

  while(now<m and cnt<n):
    nex=pow(now,2)
    if nex<m:
      ans+=nex
      now=nex
      cnt+=1
    else:
      nex=int(nex**0.5)
      break

  while(l[nex]<=1):
    now=pow(nex,2,m)
    nex=now
    if l[nex-1]==1:
      break
    else:
      l[now-1]+=1
      a.append(now)
  al=sum(l)
  amari=(n-cnt)%al
  ko=(n-cnt)//al
  ans+=ko*sum(a)+sum(a[:amari])
  print(ans)

Submission status: Wrong Answer

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

p=[0]*(M+2)
sum=[0]*(M+2)
p[X]=1
sum[1]=X
#print(1,p[X],sum[1])
f=0
for i in range(2,N+1):
    X=(X**2)%M  
    if p[X]!=0:
        j=p[X]
        f=i
        break
    else:
        sum[i]=X+sum[i-1]
        p[X]+=i
#    print(i,p[X],sum[i])

#for i in range(1,N+2):
#    if sum[i]==0:
#        break
#    else:
#        print(i,p[i],sum[i])

if f==0:
    print(sum[N])
elif i-j==1:
    print(sum[j-1])
else:
    d,mod=divmod(N-j+1,i-j)
#    print(N,j,i,d,mod,N-j+1,i-j)
    print(d*(sum[i-1]-sum[j-1])+sum[j+mod-1])

Submission status: Wrong Answer

Solution code:
N,X,M=map(int,input().split())
A=[X]
x=(A[0]**2)%M
i=0
while not x in A:
    A.append(x)
    i+=1
    x=(x**2)%M

loopid=A.index(x)
looplen=i-loopid+1
loopsum=sum(A[loopid:])
startsum=sum(A[:loopid])

ans=0
if N-1<loopid:
    ans=sum(A[:N])
else:
    loopnum=(N-1-loopid+1)//looplen if looplen else N-1-loopid
    rest=N-1-(loopid+looplen*loopnum)+1
    print(loopid,loopnum,looplen)
    print(startsum,loopsum,rest)
    ans+=startsum
    ans+=loopnum*loopsum
    ans+=sum(A[loopid:loopid+rest])
print(ans)

Submission status: Wrong Answer

Solution code:
N,X,M=map(int,input().split())
A=[X]
x=(A[0]**2)%M
i=0
while not x in A:
    A.append(x)
    i+=1
    x=(x**2)%M

loopid=A.index(x)
looplen=i-loopid+1
loopsum=sum(A[loopid:])
startsum=sum(A[:loopid])

ans=0
if N-1<loopid:
    ans=sum(A[:N])
else:
    loopnum=(N-1-loopid+1)//looplen if looplen else N-1-loopid
    rest=N-1-(loopid+looplen*loopnum)+1
    print(loopid,loopnum,looplen)
    print(startsum,loopsum,rest)
    ans+=startsum
    ans+=loopnum*loopsum
    ans+=sum(A[loopid:loopid+rest])
print(ans)

Submission status: Wrong Answer

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

A = X
ans = A

visited = [0]*M
tmp = []

i = 2
while i <= N:
    A = (A*A) % M
    if visited[A] == 0:
        visited[A] = i
        tmp.append(A)
        ans += A
    else:
        loop_length = i-visited[A]
        loop_val = sum(tmp[-1*loop_length:])
        loop_count = (N-i) // loop_length
        ans += loop_val * loop_count
        visited = [0]*M
        i += loop_length * loop_count

    i += 1

print(ans)

Submission status: Wrong Answer

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

start_loop = 0

for n in range(N):
        tmp = a[n]*a[n]%M
        if(tmp in a):
                start_loop = a.index(tmp)
                break
        a.append(tmp)

if start_loop:
        loop_num = len(a) - start_loop
        sum_before_loop = sum(a[:start_loop])
        sum_loop = sum(a[start_loop:])* (N - start_loop)//loop_num
        sum_after_loop = sum(a[start_loop: start_loop+ (N - start_loop) % loop_num])
        print(int(sum_before_loop + sum_after_loop + sum_loop))
else:
        sum_before_loop = sum(a)
        print(sum_before_loop)

Submission status: Wrong Answer

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

start_loop = 0
end_loop = 0

for n in range(N - 1):
        tmp = a[n]*a[n]%M
        if(tmp in a):
                start_loop = a.index(tmp)
                end_loop = n
                break
        a.append(tmp)

if start_loop:
        loop_num = end_loop - start_loop + 1

        sum_before_loop = sum(a[:start_loop])
        sum_loop = sum(a[start_loop: end_loop + 1])*int((N - start_loop)/ loop_num)
        sum_after_loop = sum(a[start_loop: start_loop+ (N - start_loop) % loop_num])
        print(int(sum_before_loop + sum_after_loop + sum_loop))
else:
        sum_before_loop = sum(a)
        print(sum_before_loop)

Submission status: Wrong Answer

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

start_loop = 0
end_loop = 0

for n in range(N - 1):
        tmp = a[n]*a[n]%M
        if(tmp in a):
                start_loop = a.index(tmp)
                end_loop = n
                break
        a.append(tmp)

if start_loop:
        loop_num = end_loop - start_loop + 1

        sum_before_loop = sum(a[:start_loop])
        sum_loop = sum(a[start_loop: end_loop + 1])*int((N - start_loop)/ loop_num)
        sum_after_loop = sum(a[start_loop: start_loop+ (N - start_loop) % loop_num])
        print(sum_after_loop)
        print(int(sum_before_loop + sum_after_loop + sum_loop))
else:
        sum_before_loop = sum(a)
        print(sum_before_loop)

Submission status: Wrong Answer

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

start_loop = 0
end_loop = 0

for n in range(N - 1):
        tmp = a[n]*a[n]%M
        if(tmp in a):
                start_loop = a.index(tmp)
                end_loop = n
                break
        a.append(tmp)
        print(tmp)

if start_loop:
        loop_num = end_loop - start_loop + 1

        sum_before_loop = sum(a[:start_loop])
        sum_loop = sum(a[start_loop: end_loop + 1]) * (N - start_loop)/loop_num
        sum_after_loop = sum(a[start_loop: start_loop+ (N - start_loop) % loop_num])

        print(int(sum_before_loop + sum_after_loop + sum_loop))
else:
        sum_before_loop = sum(a)
        print(sum_before_loop)

Submission status: Wrong Answer

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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
else:
    chk=[-1]*m
    asum00=[0]*m
    ai,asum=x,0
    for icnt in range(m):
        asum00[icnt]=asum
        if chk[ai]!=-1:
            icnt0=chk[ai]
            break
        chk[ai]=icnt
#        asum00[icnt]=asum
        asum+=ai
        ai=f(ai,m)
    asum0=asum00[icnt0]
        
    icntk=icnt-icnt0
    n0=n-1-icnt0
    if icntk!=1:
        nk=n0//icntk
        nr=n0%icntk
    else:
        nk=n0
        nr=-1
    asumk=asum-asum0
       
    ans=asum00[icnt0+nr+1]+asumk*nk
    print(ans)

Submission status: Wrong Answer

Solution code:
#n,x,m=map(int,input().split())
n,x,m=6,2,1001

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
else:
    chk=[-1]*m
    asum00=[0]*m
    ai,asum=x,0
    for icnt in range(m):
        asum00[icnt]=asum
        if chk[ai]!=-1:
            icnt0=chk[ai]
            break
        chk[ai]=icnt
#        asum00[icnt]=asum
        asum+=ai
        ai=f(ai,m)
    asum0=asum00[icnt0]
        
    icntk=icnt-icnt0
    n0=n-1-icnt0
    if icntk!=1:
        nk=n0//icntk
        nr=n0%icntk
    else:
        nk=n0
        nr=-1
    asumk=asum-asum0
       
    ans=asum00[icnt0+nr+1]+asumk*nk
    print(ans)

Submission status: Wrong Answer

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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
else:
    chk=[-1]*m
    asum00=[0]*m
    ai,asum=x,0
    for icnt in range(m):
        if chk[ai]!=-1:
            icnt0=chk[ai]
            break
        chk[ai]=icnt
        asum00[icnt]=asum
        asum+=ai
        ai=f(ai,m)
    asum0=asum00[icnt0]
        
    icntk=icnt-icnt0
    n0=n-1-icnt0
    if icntk!=1:
        nk=n0//icntk
        nr=n0%icntk
    else:
        nk=n0
        nr=-1
    asumk=asum-asum0
       
    ans=asum00[icnt0+nr+1]+asumk*nk
    print(ans)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
ans = 0
if x == 0:
    print(0)
    exit()
elif x == 1:
    print(n)
    exit()

while x < m:
    ans += x
    x = pow(x, 2)
    n -= 1
    if n == 0:
        print(ans)
        exit()

x = x % m
flag = [False]*m
loop_len = 0
loop = []
loop_sum = 0
while not flag[x]:
    flag[x] = True
    loop.append(x)
    loop_sum += x
    x = pow(x, 2, m)
    loop_len += 1
loop_count = n // loop_len
loop_amari = n % loop_len
ans += loop_sum*loop_count
if loop_amari != 0:
    ans += sum(loop[:loop_amari])
print(ans)

Submission status: Wrong Answer

Solution code:
N,X,M=map(int,input().split())
a=[0]*(M)
A=X%M
a[A]=1
ans=A
Ans=[A]
flag=0
for i in range(N):
    A=A*A%M
    if A==0:
        break
    if a[A]==1:
        flag=1
        break
    a[A]=1
    ans+=A
    Ans.append(A)
if flag==1:
    for num in range(len(Ans)):
        if A==Ans[num]:
            break
    n=len(Ans)-num
    b=sum(Ans[:num])
    x=(N-num)//n
    y=(N-num)%n
    Sum=b+(ans-b)*(x)+sum(Ans[num:y+num])
else:
    Sum=sum(Ans)
print(Sum)

Submission status: Wrong Answer

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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
else:
    chk=[-1]*m
    asum00=[0]*m
    ai,asum=x,0
    for icnt in range(m):
        if chk[ai]!=-1:
            icnt0=chk[ai]
            break
        chk[ai]=icnt
        asum00[icnt]=asum
        asum+=ai
        ai=f(ai,m)
    asum0=asum00[icnt0]
        
    icntk=icnt-icnt0
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0
       
    ans=asum00[icnt0+nr+1]+asumk*nk
    print(ans)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
ans = 0
while x < m:
    ans += x
    x = pow(x, 2)
    n -= 1
    if n == 0:
        print(ans)
        exit()

x = x % m
flag = [False]*m
loop_len = 0
loop = []
loop_set = set()
loop_sum = 0
while True:
    if x in loop_set:
        break
    loop_set.add(x)
    loop.append(x)
    loop_sum += x
    x = pow(x, 2, m)
    loop_len += 1

loop_count = n // loop_len
loop_amari = n % loop_len
ans += loop_sum*loop_count
if loop_amari != 0:
    ans += sum(loop[:loop_amari])
print(ans)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
count = 0
ans = 0
while x < m:
    n -= 1
    ans += x
    x = pow(x, 2)
    if n == 0:
        print(ans)
        exit()

mod = [False]*m
loop_len = 0
res = []
sum_res = 0
x = x % m
while not mod[x]:
    mod[x] = True
    res.append(x)
    sum_res += x
    x = pow(x, 2, m)
    loop_len += 1
#print(loop_len)
#print(res)
syo = n // loop_len
amari = n % loop_len
if amari == 0:
    ans += sum_res*syo
else:
    ans += sum_res*syo + sum(res[:amari])
print(ans)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
count = 0
ans = 0
while x < m:
    n -= 1
    ans += x
    x = x*x
    if n == 0:
        break
if n == 0:
    print(ans)
    exit()

mod = [False]*(m-1)
loop_len = 0
res = []
sum_res = 0
x = x % m
while not mod[x]:
    mod[x] = True
    res.append(x)
    sum_res += x
    x = pow(x, 2, m)
    loop_len += 1
#print(loop_len)
#print(res)
syo = n // loop_len
amari = n % loop_len
if amari == 0:
    ans += sum_res*syo
else:
    ans += sum_res*syo + sum(res[:amari])
print(ans)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
count = 0
ans = 0
while x < m:
    n -= 1
    ans += x
    x *= x
    if n == 0:
        break
if n == 0:
    print(ans)
    exit()

mod = [False]*(m-1)
loop_len = 0
res = []
sum_res = 0
while not mod[x%m]:
    mod[x%m] = True
    if len(res) == 0:
        res.append(x%m)
    else:
        res.append(res[-1] + x%m)
    sum_res += x%m
    x *= x
    loop_len += 1
#print(loop_len)
#print(res)
syo = n // loop_len
amari = n % loop_len
if amari == 0:
    ans += sum_res*syo
else:
    ans += sum_res*syo + res[amari-1]
print(ans)

Submission status: Wrong Answer

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

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(icnt+1):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    if icntk==0:
#        print("0:",ai,asum,icnt,ai0,asum0,icnt0)
        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
        ans=asum0+ai0*(n-icnt0)
        print(ans)       
    else:
#        print("1:",ai,asum,icnt,ai0,asum0,icnt0)
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
        ans=asum0+asumk*nk+asumr    
        print(ans)

Submission status: Wrong Answer

Solution code:

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

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(icnt+1):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    if icntk==0:
#        print("0:",ai,asum,icnt,ai0,asum0,icnt0)
        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
        ans=x*n
        print(ans)       
    else:
#        print("1:",ai,asum,icnt,ai0,asum0,icnt0)
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
        ans=asum0+asumk*nk+asumr    
        print(ans)

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
ls = [False]*M
ls_mod = []
x = X
for m in range(M+1):
  if ls[x] == False:
    ls_mod.append(x)
    ls[x] = m
    x = (x**2)%M
  else:
    last = m
    fast = ls[x]
    diff = last - fast
    break
"""if last >= N:
  print(sum(ls_mod[:N]))
else:
  shou = (N-fast) // diff
  amari = (N-fast) % diff
  print(sum(ls_mod[:fast])+sum(ls_mod[fast:])*shou+sum(ls_mod[fast:fast+amari]))

"""

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
S = [0]
F = [None] * m
for i in range(m):
    S.append(S[-1] + x)
    if F[x] is not None:
        j = F[x]
        q, r = (n - j) // (i - j), (n - j) % (i - j)
        print((S[i] - S[j]) * q + S[j + r])
        exit()
    F[x] = i
    x = pow(x, 2, m)

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
if X <= 1:
    print(X*N)
    exit()
check = [0]*(M+1)
check[X] += 1
A = X
last_count = 0
while True:
    A = (A**2)%M
    if check[A] != 0:
        last_count = sum(check)
        target_value = A
        break
    check[A] += 1
A2 = X
first_count = 0
while A2 != target_value:
    first_count += 1
    A2 = (A2**2)%M

roop_count = last_count-first_count

A3 = target_value
mass = A3
for i in range(roop_count-1):
    A3 = (A3**2)%M
    mass += A3
if roop_count == 0:
    print(N*X)
    exit()

ans = X
A = X
for i in range(min(N,first_count)-1):
    A = (A**2)%M
    ans += A
if N > first_count:
    ans += ((N-first_count)//roop_count)*mass
    A4 = target_value
    if (N-first_count)%roop_count >= 1:
        ans += A4
    for i in range(((N-first_count)%roop_count)-1):
        A4 = (A4**2)%M
        ans += A4
print(ans)

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
if X <= 1:
    print(X*N)
    exit()
check = [0]*(M+1)
check[X] += 1
A = X
last_count = 0
while True:
    A = (A**2)%M
    if check[A] != 0:
        last_count = sum(check)
        target_value = A
        break
    check[A] += 1
A2 = X
first_count = 0
while True:
    first_count += 1
    A2 = (A2**2)%M
    if A2 == target_value:
        break

roop_count = last_count-first_count

A3 = target_value
mass = A3
for i in range(roop_count-1):
    A3 = (A3**2)%M
    mass += A3
if roop_count == 0:
    roop_count = 1

ans = X
A = X
for i in range(min(N,first_count)-1):
    A = (A**2)%M
    ans += A
if N > first_count:
    ans += ((N-first_count)//roop_count)*mass
    A4 = target_value
    if (N-first_count)%roop_count >= 1:
        ans += A4
    for i in range(((N-first_count)%roop_count)-1):
        A4 = (A4**2)%M
        ans += A4
print(ans)

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
if X <= 1:
    print(X*N)
    exit()
check = [0]*(M+1)
check[X] += 1
A = X
last_count = 0
while True:
    A = (A**2)%M
    if check[A] != 0:
        last_count = sum(check)
        target_value = A
        break
    check[A] += 1
A2 = X
first_count = 0
while True:
    first_count += 1
    A2 = (A2**2)%M
    if A2 == target_value:
        break

roop_count = last_count-first_count

A3 = target_value
mass = A3
for i in range(roop_count-1):
    A3 = (A3**2)%M
    mass += A3
if roop_count == 0:
    print(N*X)
    exit()

ans = X
A = X
for i in range(min(N,first_count)-1):
    A = (A**2)%M
    ans += A
if N > first_count:
    ans += ((N-first_count)//roop_count)*mass
    A4 = target_value
    if (N-first_count)%roop_count >= 1:
        ans += A4
    for i in range(((N-first_count)%roop_count)-1):
        A4 = (A4**2)%M
        ans += A4
print(ans)

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
if X <= 1:
    print(X*N)
    exit()
check = [0]*(M+1)
check[X] += 1
A = X
last_count = 0
while True:
    A = (A**2)%M
    if check[A] != 0:
        last_count = sum(check)
        target_value = A
        break
    check[A] += 1
A2 = X
first_count = 0
while True:
    first_count += 1
    A2 = (A2**2)%M
    if A2 == target_value:
        break

roop_count = last_count-first_count

A3 = target_value
mass = A3
for i in range(roop_count-1):
    A3 = (A3**2)%M
    mass += A3
if roop_count <= 0:
    print(N*X)
    exit()

ans = X
A = X
for i in range(min(N,first_count)-1):
    A = (A**2)%M
    ans += A
if N > first_count:
    ans += ((N-first_count)//roop_count)*mass
    A4 = target_value
    if (N-first_count)%roop_count >= 1:
        ans += A4
    for i in range(((N-first_count)%roop_count)-1):
        A4 = (A4**2)%M
        ans += A4
print(ans)

Submission status: Wrong Answer

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

for i in range(m):
    if i == n or x == 0:
        ans = sum(x_list)
        print(ans)
        exit()
    x_list.append(x)
    x = (x**2)%m
    
    if x_list.count(x) == 1:
        break

for i in range(len(x_list)):
    if x_list[i] == x:
        roop = list(x_list[i:])
        if n % len(roop) == 0:
            ans = sum(roop)*(n//len(roop) - 1) + sum(x_list)
            print(ans)
        else:
            ans = sum(roop)*(n//len(roop) - 1) + sum(x_list) + sum(roop[:(n//len(roop))])
            print(ans)
        exit()

Submission status: Wrong Answer

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

ans = 0
a = [0]
id = [0]*(m+1)
l = 1
while id[x] == 0:
    a.append(x)
    id[x] = l
    ans += x
    l += 1
    x = x**2 % m

c = l - id[x]
s=0

for i in range(id[x],l):
    s += a[i]

if n < l:
    ans = sum(a)
else:
    n -= l
    n += 1
    ans += s*(n//c)
    n %= c
    for i in range(n):
        ans += a[id[x] + i]
print(ans)

Submission status: Wrong Answer

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

ans = 0
a = [0]
id = [0]*(m+1)
l = 1
while id[x] == 0:
    a.append(x)
    id[x] = l
    ans += x
    l += 1
    x = x**2 % m

c = l - id[x]
s=0

for i in range(id[x],l):
    s += a[i]

if n <= l:
    ans = sum(a)
else:
    n -= l
    n += 1
    ans += s*(n//c)
    n %= c
    for i in range(n):
        ans += a[id[x] + i]
print(ans)