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:
n, x, m = map(int, input().split())
s = x
a = x
note = [0] * m
note[a] += 1
seq = []
for i in range(n-1):
    seq.append(a)
    a = a**2 % m
    if note[a] > 0:
        ind = seq.index(a)
        l = len(seq[ind:])
        n -= len(seq[:ind])
        syo, r = divmod(n, l)
        s = s + sum(seq[ind:]) * (syo-1)
        s += sum(seq[ind:ind + r])
        print(s)
        exit()
    if a == 0:
        print(s)
        exit()
    note[a] += 1
    s += a
print(s)

if n == 6:
    print(n)

Submission status: Wrong Answer

Solution code:
import numpy as np
from sys import stdin
import copy

def main():
    input = stdin.readline
    n, x, m = 1,1,3
    a = np.array([x], dtype=np.int64)
    h = {}
    h[x] = 0
    t = 0
    for i in range(n - 1):
        t = a[i] * a[i] % m
        if t in h:
            break
        h[t] = 0
        a = np.append(a, t)
    b = copy.deepcopy(a)
    if a == t:
        a = a[:np.where(a == t)[0][0]]
    b = np.setdiff1d(b, a)
    ans = np.sum(a, dtype=np.int64)
    if len(b) > 0:
        ans += np.sum(b, dtype=np.int64) * ((n - len(a)) // len(b))
        ans += np.sum(b[0: (n - len(a)) % len(b)], dtype=np.int64)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
s = x
a = x
note = [0] * m
note[a] += 1
seq = []
for i in range(n-1):
    seq.append(a)
    a = a**2 % m
    if note[a] > 0:
        ind = seq.index(a)
        l = len(seq[ind:])
        n -= len(seq[:ind-1])
        syo = n // l
        r = n % l
        s = s + sum(seq[ind:]) * (syo-1)
        s += sum(seq[ind:ind + r - 1])
        print(s)
        exit()
    if a == 0:
        print(s)
        exit()
    note[a] += 1
    s += a
print(s)

if n == 6:
    print(n)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
s = x
a = x
note = [0] * m
note[a] += 1
seq = []
for i in range(n-1):
    seq.append(a)
    a = a**2 % m
    if note[a] > 0:
        ind = seq.index(a)
        l = len(seq[ind:])
        n -= len(seq[:ind])
        syo = n // l
        r = n % l
        s = s + sum(seq[ind:]) * (syo-1)
        for j in range(ind, ind+r-1):
            s += seq[j]
        print(s)
        exit()
    if a == 0:
        print(s)
        exit()
    note[a] += 1
    s += a
print(s)

if n == 6:
    print(n)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
s = x
a = x
note = [0] * m
note[a] += 1
seq = []
for i in range(n-1):
    seq.append(a)
    a = a**2 % m
    if note[a] > 0:
        ind = seq.index(a)
        l = len(seq[ind:])
        n -= len(seq[:ind-1])
        syo = n // l
        r = n % l
        s = s + sum(seq[ind:]) * (syo-1)
        for j in range(ind, ind+r-1):
            s += seq[j]
        print(s)
        exit()
    if a == 0:
        print(s)
        exit()
    note[a] += 1
    s += a
print(s)

if n == 6:
    print(n)

Submission status: Wrong Answer

Solution code:
N,X,M = map(int, input().split())
ans = 'No'
list = []
A = X
for i in range(N):
  A = A*A%M
  list.append(A)
  setlist = set(list)
  if len(setlist) != len(list):
    M = i
    ans = 'Yes'
    break
if ans == 'Yes':
  for j in range(M):
    if list[j] == list[M]:
      K = j
      Y = M-K
      F =(N-K)//Y
      G =(N-K)%Y
  print(X+sum(list[:K])+F*sum(list[K:M])+sum(list[K:K+G-1]))
else:
  print(X+sum(list))

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
s = x
a = x
note = [0] * m
note[a] += 1
seq = []
for i in range(n-1):
    seq.append(a)
    a = a**2 % m
    if note[a] > 0:
        ind = seq.index(a)
        l = len(seq[ind:])
        n -= len(seq[:ind-1])
        syo = n // l
        r = n % l
        s = s + sum(seq[ind:]) * (syo-1)
        if r != 0:
            for j in range(ind, ind+r-1):
                s += seq[j]
        print(s)
        exit()
    if a == 0:
        print(s)
        exit()
    note[a] += 1
    s += a
print(s)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
s = x
a = x
note = [0] * m
note[a] += 1
seq = []
for i in range(n-1):
    seq.append(a)
    a = a**2 % m
    if note[a] > 0:
        ind = seq.index(a)
        l = len(seq[ind:])
        n -= len(seq[:ind-1])
        syo = n // l
        if syo == 0:
            break
        a = n % l
        s = s + sum(seq[ind:]) * (syo-1)
        if a != 0:
            for j in range(ind, ind+a-1):
                s += seq[j]
        print(s)
        exit()
    if a == 0:
        print(s)
        exit()
    note[a] += 1
    s += a
print(s)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
s = x
a = x
note = [0] * m
note[a] += 1
seq = []
for i in range(n-1):
    seq.append(a)
    a = a**2 % m
    if note[a] > 0:
        ind = seq.index(a)
        l = len(seq[ind:])
        n -= len(seq[:ind-1])
        syo = n // l 
        a = n % l
        s = s + sum(seq[ind:]) * (syo-1)
        if a != 0:
            for j in range(ind, ind+a-1):
                s += seq[j]
        print(s)
        exit()
    if a == 0:
        print(s)
        exit()
    note[a] += 1
    s += a
print(s)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
s = x % m
a = x % m
note = []
for i in range(n-1):
    note.append(a)
    a = a**2 % m
    if a in set(note):
        ind = note.index(a)
        l = len(note[ind:])
        n -= len(note[:ind-1])
        syo = n // l 
        a = n % l
        s = s + sum(note[ind:]) * (syo-1)
        if a != 0:
            for j in range(ind, ind+a-1):
                s += note[j]
        print(s)
        exit()
    s += a
    if a == 0:
        print(s)
        exit()

print(s)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n, x, m = tin()
	#s = input()	
	dd=dict()
	dd[x]=0
	rr=[0]*(m+1)
	ret=x
	rr[0]=x
	nx=x
	for i in range(2, n+1):
		nx = (nx*nx) % m
		if nx in dd:
			ret += nx
			break
		else:
			dd[nx] = i
		ret += nx
		rr[i-1]=ret
	else:
		return ret
	
	loop_size = i-dd[nx]
	loop_value = ret - (rr[dd[nx]-1] if dd[nx]>0 else 0)
	#pa(dd)
	ret += ((n-i)//loop_size)*loop_value
	for _ in range((n-i)%loop_size):
		nx = (nx*nx)%m
		ret += nx
	return ret
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n, x, m = tin()
	#s = input()	
	dd=dict()
	dd[x]=0
	rr=[0]*(m+1)
	ret=x
	rr[0]=x
	nx=x
	for i in range(2, n+1):
		nx = (nx*nx) % m
		if nx in dd:
			ret += nx
			break
		else:
			dd[nx] = i
		ret += nx
		rr[i-1]=ret
	else:
		return ret
	
	cc=0
	loop_size = i-dd[nx]
	loop_value = ret - rr[dd[nx]-1]
	#pa(dd)
	ret += ((n-i)//loop_size)*loop_value
	for _ in range((n-i)%loop_size):
		nx = (nx*nx)%m
		ret += nx
	return ret
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
from collections import OrderedDict
def solve(N,X,M):
    A=X
    ans=A
    if N==1:
        return ans
    if N==2:
        return ans+f(A,M)
    seen=set()
    order_seen=[]
    for i in range(2,N+1):
        A=f(A,M)
        if i!=2:
            if A not in seen:
                seen.add(A)
                order_seen.append(A)
            else:  # If A has already been seen we are just going to repeat so break out of the loop.
                i-= 1 # Correcting factor for fact that when we break out of the loop we go one above with i
                break
        if A==0:   # If A=0 it will repeat forever.
            return ans
        ans+=A
    n=len(order_seen)
    N-=i
    mult_factor=N//n
    total_sum_seen=sum(order_seen)
    ans+=(total_sum_seen*mult_factor)
    number_remaining=N%n
    for i in range(number_remaining):
        ans+=order_seen[i]
    return ans

# The function for the recurrence relation.  A_n+1=A_n^2%M
def f(A,M):
    return A**2%M

N,X,M=readMap()
print(solve(N,X,M))

Submission status: Wrong Answer

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

def input_int_array():
    return map(int, input().split())


def find_index(a, x, count):
    for i in range(count):
        if a[i] == x:
            return i
    return -1


def answer(n, x, m):
    a1 = x
    ai = a1
    loop_start = -1
    loop_end = n
    a[1] = a1
    ans = a1
    for i in range(2, n + 1):
        ai = ai*ai % m
        a.append(ai)
        ans += ai
        index = find_index(a, ai, i)
        for j in range(1, i):
            if a[j] == ai:
                loop_start = index
                loop_end = i
                break
        if loop_start >= 0:
            break
    if loop_start < 0:
        print(ans)
        return
    ans -= ai
    loop_count, remaining = divmod(n - (loop_start - 1), loop_end - loop_start)
    if loop_count > loop_start:
        start_ans = 0
        for i in range(1, loop_start):
            start_ans += a[i]
        loop_sum = ans - start_ans
        ans += loop_sum * (loop_count-1)
        for i in range(loop_start, loop_start + remaining):
            ans += a[i]
    else:
        for i in range(loop_start, loop_end):
            if i < remaining:
                ans += a[i]
            loop_sum += a[i]
        ans += loop_sum * (loop_count-1)
    print(ans)


n, x, m = input_int_array()
a = [0, 0]

answer(n, x, m)

Submission status: Wrong Answer

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

def input_int_array():
    return map(int, input().split())


def f(x, m):
    return x % m


def find_index(a, x, count):
    for i in range(count):
        ai = a[i]
        if ai == x:
            return i
    return -1


def answer(n, x, m):
    a1 = x
    ai = a1
    loop_start = 0
    loop_end = n
    a[1] = a1
    for i in range(2, n + 1):
        ai = f(ai**2, m)
        a[i] = ai
        index = find_index(a, ai, i)
        if index >= 0:
            loop_start = index
            loop_end = i
            break
    ans = 0
    for i in range(1, loop_start):
        ans += a[i]
    loop_sum = 0
    for i in range(loop_start, loop_end):
        loop_sum += a[i]
    loop_count, remaining = divmod(n - (loop_start - 1), loop_end - loop_start)
    ans += loop_sum * loop_count
    for i in range(loop_start, loop_start + remaining):
        ans += a[i]
    print(ans)


n, x, m = input_int_array()
a = [-2] * (100000000)

answer(n, x, m)

Submission status: Wrong Answer

Solution code:
N,X,M=map(int, input().split())
import time
from math import log, ceil



ini=[0]*M
mod=[0]*M
ini[0]=sum(list(range(1,M)))
Counter=[0]*M
Counter[0]=M-1

for i in range(1,M):
    now=i+1
    temp=now
    count=1
    while now**2<M:
        now=now**2
        temp+=now
        count+=1
    m=(now**2)%M
    ini[i]=temp
    mod[i]=m
    Counter[i]=count
#print(ini[:5])
#print("ok")
#print(Counter[:100])
ans=0
count=0
now=X
done=[-1]*M
ok=False
while True:
    if now==0:
        print(ans)
        exit()
    if count+Counter[now-1]>N:
        break
    if done[now-1]==-1 or ok is True:
        done[now-1]=(ans, count)
        ans+=ini[now-1]
        #print(ini[now-1])
        count+=Counter[now-1]
        now=mod[now-1]
    else:
        pans, pcount=done[now-1]
        #print(count, pcount)
        #print("break")
        ans+=(ans-pans)*((N-count)//(count-pcount))
        count+=(count-pcount)*((N-count)//(count-pcount))+1
        #print(count)
        ok=True


print(ans, count, now, )



while True:
    if count==N:
        break

    ans+=now%M
    now=(now**2)%M
    count+=1

    

print(ans)






#print(ini)
#print(mod)
#print(Counter)

Submission status: Wrong Answer

Solution code:
N,X,M=map(int, input().split())
import time
from math import log, ceil



ini=[0]*M
mod=[0]*M
ini[0]=sum(list(range(1,M)))
Counter=[0]*M
Counter[0]=M-1

for i in range(1,M):
    now=i+1
    temp=now
    count=1
    while now**2<M:
        now=now**2
        temp+=now
        count+=1
    m=(now**2)%M
    ini[i]=temp
    mod[i]=m
    Counter[i]=count
#print(ini[:5])
#print("ok")
#print(Counter[:100])
ans=0
count=0
now=X
done=[-1]*M
ok=False
while True:
    if now==0:
        print(ans)
        exit()
    if count+Counter[now-1]>N:
        break
    if done[now-1]==-1 or ok is True:
        done[now-1]=(ans, count)
        ans+=ini[now-1]
        #print(ini[now-1])
        count+=Counter[now-1]
        now=mod[now-1]
    else:
        pans, pcount=done[now-1]
        #print(count, pcount)
        #print("break")
        ans+=(ans-pans)*((N-count)//(count-pcount))
        count+=(count-pcount)*((N-count)//(count-pcount))
        #print(count)
        ok=True


#print(ans, count)



if count!=N:
    for i in range(100000000000):
        print(1)


while True:
    if count==N:
        break

    ans+=now%M
    now=(now**2)%M
    count+=1

    

print(ans)

Submission status: Wrong Answer

Solution code:
N,X,M=map(int, input().split())
import time
from math import log, ceil



ini=[0]*M
mod=[0]*M
ini[0]=sum(list(range(1,M)))
Counter=[0]*M
Counter[0]=M-1

for i in range(1,M):
    now=i+1
    temp=now
    count=1
    while now**2<M:
        now=now**2
        temp+=now
        count+=1
    m=(now**2)%M
    ini[i]=temp
    mod[i]=m
    Counter[i]=count
#print(ini[:5])
#print("ok")
#print(Counter[:100])
ans=0
count=0
now=X
done=[-1]*M
ok=False
while True:
    if now==0:
        print(ans)
        exit()
    if count+Counter[now-1]>N:
        break
    if done[now-1]==-1 or ok is True:
        done[now-1]=(ans, count)
        ans+=ini[now-1]
        #print(ini[now-1])
        count+=Counter[now-1]
        now=mod[now-1]
    else:
        pans, pcount=done[now-1]
        #print(count, pcount)
        #print("break")
        ans+=(ans-pans)*((N-count)//(count-pcount))
        count+=(count-pcount)*((N-count)//(count-pcount))
        #print(count)
        ok=True


#print(ans, count)



    


while True:
    if count==N:
        break
    time.sleep(30)
    print("keep")
    ans+=now%M
    now=(now**2)%M
    count+=1

    

print(ans)

Submission status: Wrong Answer

Solution code:
N,X,M=map(int, input().split())
import time
from math import log, ceil



ini=[0]*M
mod=[0]*M
ini[0]=sum(list(range(1,M)))
Counter=[0]*M
Counter[0]=M-1

for i in range(1,M):
    now=i+1
    temp=now
    count=1
    while now**2<M:
        now=now**2
        temp+=now
        count+=1
    m=(now**2)%M
    ini[i]=temp
    mod[i]=m
    Counter[i]=count
#print(ini[:5])
#print("ok")
#print(Counter[:100])
ans=0
count=0
now=X
done=[-1]*M
ok=False
while True:
    if now==0:
        print(ans)
        exit()
    if count+Counter[now-1]>N:
        break
    if done[now-1]==-1 or ok is True:
        done[now-1]=(ans, count)
        ans+=ini[now-1]
        #print(ini[now-1])
        count+=Counter[now-1]
        now=mod[now-1]
    else:
        pans, pcount=done[now-1]
        #print(count, pcount)
        #print("break")
        ans+=(ans-pans)*((N-count)//(count-pcount))
        count+=(count-pcount)*((N-count)//(count-pcount))
        #print(count)
        ok=True


#print(ans, count)



    


while True:
    if count==N:
        break
    time.sleep(3)
    ans+=now%M
    now=(now**2)%M
    count+=1

    

print(ans)

Submission status: Wrong Answer

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

from math import log, ceil



ini=[0]*M
mod=[0]*M
ini[0]=sum(list(range(1,M)))
Counter=[0]*M
Counter[0]=M-1

for i in range(1,M):
    now=i+1
    temp=now
    count=1
    while now**2<M:
        now=now**2
        temp+=now
        count+=1
    m=(now**2)%M
    ini[i]=temp
    mod[i]=m
    Counter[i]=count
#print(ini[:5])
#print("ok")
#print(Counter[:100])
ans=0
count=0
now=X
done=[-1]*M
ok=False
while True:
    if now==0:
        print(ans)
        exit()
    if count+Counter[now-1]>N-2:
        break
    if done[now-1]==-1 or ok is True:
        done[now-1]=(ans, count)
        ans+=ini[now-1]
        #print(ini[now-1])
        count+=Counter[now-1]
        now=mod[now-1]
    else:
        pans, pcount=done[now-1]
        #print(count, pcount)
        #print("break")
        ans+=(ans-pans)*((N-count)//(count-pcount))
        count+=(count-pcount)*((N-count)//(count-pcount))
        #print(count)
        ok=True


#print(ans, count)



    


while True:
    if count==N:
        break
    ans+=now%M
    now=(now**2)%M
    count+=1

    

print(ans)

Submission status: Wrong Answer

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

from math import log, ceil



ini=[0]*M
mod=[0]*M
ini[0]=sum(list(range(1,M)))
Counter=[0]*M
Counter[0]=M-1

for i in range(1,M):
    now=i+1
    temp=now
    count=1
    while now**2<M:
        now=now**2
        temp+=now
        count+=1
    m=(now**2)%M
    ini[i]=temp
    mod[i]=m
    Counter[i]=count
#print(ini[:5])
#print("ok")
#print(Counter[:100])
ans=0
count=0
now=X
done=[-1]*M
ok=False
while True:
    if now==0:
        print(ans)
        exit()
    if count+Counter[now-1]>N-2:
        break
    if done[now-1]==-1 or ok is True:
        done[now-1]=(ans, count)
        ans+=ini[now-1]
        #print(ini[now-1])
        count+=Counter[now-1]
        now=mod[now-1]
    else:
        pans, pcount=done[now-1]
        #print(count, pcount)
        #print("break")
        ans+=(ans-pans)*((N-count)//(count-pcount))
        count+=(count-pcount)*((N-count)//(count-pcount))
        #print(count)
        ok=True


#print(ans, count)



    


while True:
    if count==N:
        break
    ans+=now
    now=(now**2)%M
    count+=1

    

print(ans)

Submission status: Wrong Answer

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

from math import log, ceil



ini=[0]*M
mod=[0]*M
ini[0]=sum(list(range(1,M)))
Counter=[0]*M
Counter[0]=M-1

for i in range(1,M):
    now=i+1
    temp=now
    count=1
    while now**2<=M:
        now=now**2
        temp+=now
        count+=1
    m=now**2%M
    ini[i]=temp
    mod[i]=m
    Counter[i]=count
#print(ini[:5])
#print("ok")
#print(Counter[:100])
ans=0
count=0
now=X
done=[-1]*M
ok=False
while True:
    if now==0:
        print(ans)
        exit()
    if count+Counter[now-1]>N:
        break
    if done[now-1]==-1 or ok is True:
        done[now-1]=(ans, count)
        ans+=ini[now-1]
        #print(ini[now-1])
        count+=Counter[now-1]
        now=mod[now-1]
    else:
        pans, pcount=done[now-1]
        #print(count, pcount)
        #print("break")
        ans+=(ans-pans)*((N-count)//(count-pcount))
        count+=(count-pcount)*((N-count)//(count-pcount))
        #print(count)
        ok=True






    


while True:
    if count==N:
        break
    ans+=now
    now=now**2
    count+=1

    

print(ans)

Submission status: Wrong Answer

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

from math import log, ceil



ini=[0]*M
mod=[0]*M
ini[0]=sum(list(range(1,M)))
Counter=[0]*M
Counter[0]=M-1

for i in range(1,M):
    now=i+1
    temp=now
    count=1
    while now**2<M:
        now=now**2
        temp+=now
        count+=1
    m=now**2%M
    ini[i]=temp
    mod[i]=m
    Counter[i]=count
#print(ini[:5])
#print("ok")
#print(Counter[:100])
ans=0
count=0
now=X
done=[-1]*M
ok=False
while True:
    if now==0:
        print(ans)
        exit()
    if count+Counter[now-1]>N:
        break
    if done[now-1]==-1 or ok is True:
        done[now-1]=(ans, count)
        ans+=ini[now-1]
        #print(ini[now-1])
        count+=Counter[now-1]
        now=mod[now-1]
    else:
        pans, pcount=done[now-1]
        #print(count, pcount)
        #print("break")
        ans+=(ans-pans)*((N-count)//(count-pcount))
        count+=(count-pcount)*((N-count)//(count-pcount))
        #print(count)
        ok=True






    


while True:
    if count==N:
        break
    ans+=now
    now=now**2
    count+=1

    

print(ans)






#print(ini)
#print(mod)
#print(Counter)

Submission status: Wrong Answer

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

from math import log, ceil
if X==0:
    print(0)
    exit()
ans=0

ini=[0]*M
mod=[0]*M
ini[0]=sum(list(range(1,M)))
Counter=[0]*M
Counter[0]=M-1

for i in range(1,M):
    now=i+1
    temp=now
    count=1
    while now**2<M:
        now=now**2
        temp+=now
        count+=1
    m=now**2%M
    ini[i]=temp
    mod[i]=m
    Counter[i]=count
#print(ini[:5])
#print("ok")
#print(Counter[:100])
ans=0
count=0
now=X
done=[-1]*M
ok=False
while True:
    if count+Counter[now-1]>N:
        break
    if done[now-1]==-1 or ok is True:
        done[now-1]=(ans, count)
        ans+=ini[now-1]
        #print(ini[now-1])
        count+=Counter[now-1]
        now=mod[now-1]
    else:
        pans, pcount=done[now-1]
        #print(count, pcount)
        #print("break")
        ans+=(ans-pans)*((N-count)//(count-pcount))
        count+=(count-pcount)*((N-count)//(count-pcount))
        #print(count)
        ok=True
    if now==0:
        print(ans)
        exit()





    


while True:
    if count==N:
        break
    ans+=now
    now=now**2
    count+=1

    

print(ans)






#print(ini)
#print(mod)
#print(Counter)

Submission status: Wrong Answer

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

from math import log, ceil

ans=0

ini=[0]*M
mod=[0]*M
ini[0]=sum(list(range(1,M)))
Counter=[0]*M
Counter[0]=M-1

for i in range(1,M):
    now=i+1
    temp=now
    count=1
    while now**2<M:
        now=now**2
        temp+=now
        count+=1
    m=now**2%M
    ini[i]=temp
    mod[i]=m
    Counter[i]=count
#print(ini[:5])
#print("ok")
#print(Counter[:100])
ans=0
count=0
now=X
done=[-1]*M
ok=False
while True:
    if count+Counter[now-1]>N:
        break
    if done[now-1]==-1 or ok is True:
        done[now-1]=(ans, count)
        ans+=ini[now-1]
        #print(ini[now-1])
        count+=Counter[now-1]
        now=mod[now-1]
    else:
        pans, pcount=done[now-1]
        #print(count, pcount)
        #print("break")
        ans+=(ans-pans)*((N-count)//(count-pcount))
        count+=(count-pcount)*((N-count)//(count-pcount))
        #print(count)
        ok=True
    if now==0:
        print(ans)
        exit()





    


while True:
    if count==N:
        break
    ans+=now
    now=now**2
    count+=1

    

print(ans)






#print(ini)
#print(mod)
#print(Counter)

Submission status: Wrong Answer

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

cnt = 0
ruiseki = [x]
a = x
al = {}
al[x] = 0
loop_s = 0
loop_e = 0

for i in range(n - 1):
    na = (a ** 2) % m
    if na in al.keys():
        loop_s = al[na]
        loop_e = al[a]
        break
    else:
        al[na] = i + 1
        ruiseki.append(ruiseki[cnt] + na)
        cnt += 1
        a = na

if loop_e != 0:
    if loop_s - 1 < 0:
        ruiseki[0] = 0
    ans = ruiseki[max(0, loop_s - 1)]
    ans += (ruiseki[loop_e] - ruiseki[max(0, loop_s - 1)]) * ((n - loop_s) // (loop_e - loop_s + 1))
    p = max(0, n - ((n - loop_s) // (loop_e - loop_s + 1) * (loop_e - loop_s + 1)) - (loop_s - 1) - 1)
    ans += ruiseki[max(0, p + loop_s - 1)] - ruiseki[max(0, loop_s - 1)]
else:
    ans = ruiseki[-1]

print(ans)

Submission status: Wrong Answer

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

A_change_list = [0] * (M + 1)
check_list = [0] * (M + 1)

for i in range(1, M + 1):
    A_change_list[i] = i**2 % M

A = X
count = 0
sum_value = 0
ans = 0
for i in range(1, N + 1):
    if check_list[A] != 2:
        if check_list[A] == 1:
            count += 1
            sum_value += A
        ans += A
        check_list[A] += 1
        A = A_change_list[A]
    else:
        if A == 0:
            break
        elif A == 1:
            ans += N - i
            break
        else:
            div, mod = divmod((N - i), count)
            ans += sum_value * div
            for _ in range(mod + 1):
                ans += A
                A = A_change_list[A]
            break

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math
import itertools

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,x,m = readInts()
an = x
ans = an
moddict = {an:1}
for i in range(2,n+1):
	an = pow(an,2,m)
	ans += an
	if an in moddict:
		break
	else:
		moddict[an]=i

if an in moddict:
	rep = (n-len(moddict))//(len(moddict)-moddict[an]+1)
	rem = (n-len(moddict))%(len(moddict)-moddict[an]+1)
	#print(rep,rem)
	rep_sum = 0
	boo = 0
	for key in moddict:
		if boo or key==an:
			boo = 1
			rep_sum+=key

	ans += rep_sum*rep
	for i in range(rem):
		ans+=an
		an=pow(an,2,m)


print(ans)

Submission status: Wrong Answer

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

def func(a,b):
  return pow(a,2,b)

for i in range(N):
  if i == 0:
    L.append(A)
  else:
    A = func(A,M)
    if A in L:
            
      p = L.index(A)
      q = len(L)
      L0 = L[:p]
      L1 = L[p:]
      
      r = (N-p)/(q-p)
      s = (N-p)%(q-p)
      
      print(int(sum(L0) + sum(L1)*r + sum(L1[:s-1])))
      exit()
    L.append(A)
    
print(sum(L))

Submission status: Wrong Answer

Solution code:
n, x, m = map(int,input().split())
li = [0]*(m+1)

cnt1 = 0
cnt2 = 0
ans1 = x
ans2 = 0
ans3 = 0
a = x
flag = 0
li_1 = []

for i in range(1,n):
    a = (a**2)%m
    li[a] += 1
    if li[a] == 2:
        cnt2 += 1
        ans2 += a
        flag = 1
        li_1.append(a)

    elif li[a] == 3:
        flag = 2
        break

    else:
        ans1 += a
        cnt1 += 1

# print(flag)
# # print(li)

if flag == 0:
    print(ans1)

elif flag ==1:
    print(ans1+ans2)

else:
    I = len(li_1)
    v = (n-cnt1+cnt2)%I
    for i in range(v-1):
        ans3 += li_1[i]
    print(ans1-ans2+sum(li_1)*(n-cnt1+cnt2)//cnt2+ans3)

Submission status: Wrong Answer

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

ans = X
A = X
TF = True
srt = 1000000
retu = [X]
d = dict()
d[X] = 0
loop = X
for i in range(1,N+1):
    if TF:
        A = A**2 % M
        if d.get(A) != None:
          srt = d[A]
          goal = i
          TF = False
          
        if TF:
          retu.append(A)
          loop += A
          d[A] = i
    else:
      break
      
if N-1 > srt:
    n = (N-srt)//(goal-srt+1)
    saisyo = sum(retu[:srt])
    loop -= saisyo
    print(saisyo + loop*n + sum(retu[srt:N-n*(goal-srt+1)]))
    
else:
    print(sum(retu[:N]))

Submission status: Wrong Answer

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

ans = X
A = X
TF = True
srt = 1000000
retu = [X]
d = dict()
d[X] = 0
loop = X
for i in range(1,N):
    if TF:
        A = A**2 % M
        if d.get(A) != None:
          srt = d[A]
          goal = i
          TF = False
          break   
        if TF:
          retu.append(A)
          loop += A
          d[A] = i
    else:
      break
      
if N-1 > srt:
    n = (N-srt)//(goal-srt+1)
    saisyo = sum(retu[:srt])
    loop -= saisyo
    print(saisyo + loop*n + sum(retu[srt:N-n*(goal-srt+1)]))
    
else:
    print(sum(retu[:N]))

Submission status: Wrong Answer

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

for i in range(M):
    z = A[i]**2 % M
    if z not in A:
        A.append(z)
    else:
        break


idx = A.index(z)
before = A[:idx]
cy_sum = sum(A[idx:])
cy_len = len(A[idx:])
cy_cnt = (N-len(before)) // cy_len
mod = A[idx:idx + N - len(before)-cy_len*cy_cnt]

if cy_cnt == 0:
    print(sum(A))
else:
    print(sum(before) + cy_sum*cy_cnt + sum(mod))

Submission status: Wrong Answer

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

ans = X
A = X
TF = True
srt = 1000000
retu = [X]
d = dict()
d[X] = 0
loop = X
for i in range(N-1):
    if TF:
        A = A**2 % M
        if d.get(A) != None:
          srt = d[A]
          goal = i
          TF = False
          break   
        if TF:
          retu.append(A)
          loop += A
          d[A] = i
    else:
      break
      
if N-1 > srt:
    n = (N-srt)//(goal-srt+1)
    saisyo = sum(retu[:srt])
    loop -= saisyo
    print(saisyo + loop*n + sum(retu[srt:N-n*(goal-srt+1)]))
    
else:
    print(sum(retu[:N]))

Submission status: Wrong Answer

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

dic = {}
tmp = []

a = x
sum_a = 0
for i in range(n):
    if a in dic:
        tmp.append(sum_a + a)
        idx0 = dic[a]
        idx1 = i
        period = idx1 - idx0
        times = (n - idx0) // period
        res = (n - idx0) % period
        before = tmp[idx0]
        if idx0 > 1:
            ans = tmp[idx0 - 1 + res] + (tmp[idx1] - tmp[idx0]) * times
            print(ans)
        else: # idx0 == 0 
            ans = (tmp[idx1] - tmp[idx0]) * times
            print(ans)
        break
    else:
        sum_a += a
        tmp.append(sum_a)
        dic[a] = i
        a = a ** 2 % m
else:
    print(sum_a)

Submission status: Wrong Answer

Solution code:
N,X,M=map(int,input().split())
A = [X,]
setA = {X,}
alast=X
flag=False
for i in range(min(N-1,M)):
    P=alast**2%M
    if P in setA:
        flag=True
        d = A.index(P)
        C=A[d:]
        alast=P
        break
    else:
        A.append(P)
        setA.add(P)
        alast=P
if flag:
    if alast==0:
        ans = sum(C)
    else:
        res = (N-d)%len(C)
        ans = sum(A[:d])+((N-d)//len(C))*sum(C) + sum(C[:res])
else:
    ans = sum(A) 
print(ans)