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())
check = [False] * (10**5 + 10)
check_list = [x]
a = x
check[a] = True
rooplen = 0
# ans = a
# ループを見つける
for i in range(n):
    # print('A' + str(i + 1), a)
    a = a * a % m
    if check[a]:
        break
    check[a] = True
    check_list.append(a)
    # ans += a
    rooplen += 1
# print(ans)

# ループの長さを算出
index = check_list.index(a)
# print(index)
roop_bef = check_list[0:index]
roop = check_list[index:]

# print(roop_bef, roop)

roop_bef_num = len(roop_bef)
roop_num = (n - len(roop_bef)) // len(roop)
roop_after_num = (n - len(roop_bef)) % len(roop)

ans = sum(roop_bef) + sum(roop) * roop_num + sum(check_list[:roop_after_num])
# print(check_list[:roop_after_num])

# print(rooplen)
print(ans)

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
A = [X]
a = X
s = X
r = 0
r0 = 0
l = 0
amari = 0

for i in range(N-1):
  if A.count(a ** 2 % M) >= 1:
    if a == 0:
      s = sum(A)
      break
    else:
      r0 = A.index(a)
      l = len(A[r0:])
      r = (N - i - 1) // l
      amari = (N - i - 1) % l
      s = s + sum(A[r0:])*r + sum(A[r0:r0+amari])
      break
  A.append(a**2 % M)
  s += A[-1]

print(s)

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
st = x
ans = 0
mod = m
num = []
for i in range(n):
    ch = st
    if st in num:
        break
    ans += ch
    st *= st
    st %= mod
    if i != 0 and i != 1:
        num.append(ch)
le = len(num)
if len(num) == 0:
    z = 0
else:
    z  = n//le
if le == 0:
    rest = 0
else:
    rest = (n-1)%le
if 0 in num:
    print(sum(num[:n]) + x%mod + x**2%mod)
else:
    print(z*sum(num) + sum(num[:rest-1]) + x%mod + x**2%mod)

Submission status: Wrong Answer

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


def check(X, M):
    re = X ** 2 % M
    return re


check2 = X
cnt = 0
while keep != check2:
    check2 = check(check2 ** 2, M)
    lis.append(check2)
    cnt += 1

N1 = cnt % N
N2 = cnt // N
print(sum(lis[:N1])+ N2 * sum(lis))

Submission status: Wrong Answer

Solution code:
def main():
    N, X, M = map(int, input().split())
    if N == 1:
        print(X)
        exit()
    mod_set = set([X])
    mod_list = [X]
    zero_flag = False
    repeat_idx = 0
    for _ in range(M+1):
        mod = (mod_list[-1] ** 2) % M
        if mod == 0:
            zero_flag = True
            break
        if mod in mod_set:
            repeat_idx = mod_list.index(mod)
            break
        mod_set.add(mod)
        mod_list.append(mod)

    if len(mod_list) >= N:
        print(sum(mod_list))
    elif zero_flag is True:
        print(sum(mod_list))
    else:
        print(
            sum(mod_list[:repeat_idx]) +\
                sum(mod_list[repeat_idx:]) * ((N - repeat_idx) // len(mod_list[repeat_idx:])) +\
                    sum(mod_list[repeat_idx:repeat_idx + (N - repeat_idx)%len(mod_list[repeat_idx:])]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n,x,m = map(int,input().split())
    amari = [0 for i in range(m)]
    amari[x%m] = 1
    loop = [x%m]
    while True:
        x = x**2 % m
        if amari[x]==0:
            loop.append(x)
            amari[x] = 1
        else:
            break
    ans = 0
    l = n//len(loop)
    ans += l*sum(loop)
    ans += sum(loop[:n%len(loop):])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N,X,M  = map(int,input().split())
    # N,X,M = 6, 2, 1001

    li1 = [-1 for i in range(M)]
    li2 = [] 
    li1[X] = 1
    li2.append(X)

    cnt = 2
    for i in range(N-1):
        bfr = X
        X = (X**2)%M
        

        if li1[X]!=-1:
            break
        else:
            li1[X]=cnt
            li2.append(X)
        cnt += 1
    else:
        ans = 0
        for i in range(M):
            if li1[i]!=-1:
                ans += i
        print(ans)
        return

    mm = cnt-li1[X]
    
    ans = ((N-(li1[X]-1))//mm)*sum(li2[li1[X]-1:])
    # print(li2[li1[X]-1:])

    ans += sum(li2[:li1[X]-1])

    mm2 = (N-(li1[X]-1))%mm
    ans += sum(li2[li1[X]-1:mm2+1])
    print(ans)
    # print(li1)

    # print(li2)
main()

Submission status: Wrong Answer

Solution code:
def resolve():
    n, x, m = map(int, input().split())
    a = [None] * m
    s = [x]
    a[x] = 0
    ans = x
    for i in range(1, n):
        x = pow(x, 2, m)
        if a[x] is None:
            ans += x
            a[x] = i
            s.append(ans)
        else:
            past = a[x]
            d = i - past
            ans += x
            s.append(ans)
            diff = s[i] - s[past]
            ans += ((n - i) // d) * diff
            ans += s[past + ((n - i) % d)] - s[past]
            break
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
aaa=input("").split(" ")
n=int(aaa[0])
x=int(aaa[1])
m=int(aaa[2])
lista=[x]
a=x
if(n>m):
    while (True):
        
        b=(a**2)%m
        a=b
        if(a in lista):
            
            break
        lista+=[a]
    at=sum(lista)
    ta=len(lista)
    dex=lista.index(a)
    listb=lista[dex:]
   
    tt=sum(listb)
    tb=len(listb)
    s=at-tt+x
    
    new=n-ta-1
    s+=(new//tb)*tt
    for i in range(new%tb):
        s+=listb[i]
    print(s)
    

    
    
else:
    s=x
    
    for i in range(n-1):
        b=(a**2)%m
        a=b
        s+=a
        
    print(s)

Submission status: Wrong Answer

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

ans = [X]
for n in range(N):
  X = pow((X % M),2)%M

  if X == 0 or X in ans:
    break
  else:
    ans.append(X)

print(sum(ans))

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
a = [x]
s = {x}
ans = x
re = 1
for i in range(n-1):
	a.append((a[i]*a[i])%m)
	re +=1
	ans += a[i+1]
	if a[i+1] in s:
		break
	s.add(a[i+1])
else:
	print(ans)
	exit()
ans -= a[i+1]
del a[i+1]
k = n//re
n = n%re
ans += k*ans
for i in range(n):
	ans += a[i]
print(ans)

Submission status: Wrong Answer

Solution code:
N,X,M=map(int,input().split())
L = [X]
now = X
ans = X
for i in range(1,N):
  now = now**2%M
  if now == 0:
    print(ans)
    exit()
  ans += now
  if now in L:
    f = L.index(now)
    l = i-f
    ans = ans + sum(L[f:i])*( (N-f)//l )
    for j in range((N-f)%l):
      now = now**2%M
      ans += now
      print(ans)
      exit()
    break
  else:
    L.append(now)
print(ans)

Submission status: Wrong Answer

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

amari_count = [0]*m
amari_count[x] += 1
flag = -1
zero = False
#その時の余りと、答えの累積和
amari_list =[x]
sm = [x]
for i in range(min(n-1,m)):
    amari = (amari_list[i]**2)%m
    amari_list.append(amari)
    sm.append(sm[i]+amari)
    if amari_count[amari]>0:
        flag = amari
        idx = i
        break
    else:
        amari_count[amari] += 1
    if amari == 0:
        zero = True
        break

if flag < 0 or zero:
    ans = sm[-1]
else:
    ans = 0
    for i in range(len(sm)):
        if amari_list[i]==flag:
            if i > 0:
                left = i
                ans += sm[left-1]
                interval = idx-left+1
            else:
                left = 0
                interval = idx +1
            break

    loop_sum = sm[idx]-sm[left-1]
    loop_count = (n-left)//interval
    hamidashi = (n-left)%interval
    ans += loop_sum*loop_count
    if hamidashi >0:
        ans += sm[left+hamidashi-1]-sm[left-1]

print(ans)

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
st = x
ans = 0
mod = m
num = []
for i in range(n):
    ch = st
    if st in num:
        break
    ans += ch
    st *= st
    st %= mod
    if i != 0 and i != 1:
        num.append(ch)
le = len(num)
if len(num) == 0:
    z = 0
else:
    z  = n//le
if le == 0:
    rest = 0
else:
    rest = (n-1)%le
if 0 in num:
    print(sum(num[:n]) + x + x**2%mod)
else:
    print(z*sum(num) + sum(num[:rest-1]) + x + x**2%mod)

Submission status: Wrong Answer

Solution code:

N,X,M = map(int,input().split())
ans = X
X1 = X
check1 = 0
repeat1 = 0
go1 = 0
list1 = [10]
for i in range(2,N+1):
    mid1 = (X1*X1)%M
    list1.append(mid1)
    if X1*X1 > M:
        check1 += 1
    if check1 ==0:
        repeat1 = X1*X1
        point1 = i
    if check1 >1:
        if mid1 == repeat1:
            point2 = i
            go1 = 1
            break
    if check1 == 1:
        if mid1 == repeat1:
            print("stop1111")
    #print("mid1",mid1)
    ans += mid1
    X1=mid1

if go1 == 1:
    t1 = point2-point1
    ans = (N-point1)//t1*sum(list1[point1-1:point2-1])+sum(list1[:point1])+sum(list1[point1-1:point1-1+(N-point1)%t1+1])
print(ans)

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
def jouken(a,waru):
    return a**2%waru
ni = 0
num =0
for i in range(n-1):
    ni = x
    if i ==0:
        num+=x
    x = jouken(ni,m)
    num+=x
print(num)

Submission status: Wrong Answer

Solution code:
def main():
    N,X,M  = map(int,input().split())
    # N,X,M = 6, 2, 1001

    li1 = [-1 for i in range(M)]
    li2 = [] 
    li1[X] = 1
    li2.append(X)

    cnt = 2
    for i in range(N-1):
        bfr = X
        X = (X**2)%M
        

        if li1[X]!=-1:
            break
        else:
            li1[X]=cnt
            li2.append(X)
        cnt += 1
    else:
        ans = 0
        for i in range(M):
            if li1[i]!=-1:
                ans += i
        print(ans)
        return

    mm = cnt-li1[X]
    
    ans = ((N-(li1[X]-1))//mm)*sum(li2[li1[X]-1:])
    # print(li2[li1[X]-1:])

    ans += sum(li2[:li1[X]-1])

    mm2 = (N-(li1[X]-1))%mm
    ans += sum(li2[li1[X]-1:mm2])
    print(ans)
    # print(li1)

    # print(li2)
main()

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
x = X
nums = []
isSearched = [False] * (M+1)
isSearchedNums = [-1] * (M+1)
n = 0
looped = 0
while True:
    x = (x*x) % M
    if isSearched[x]:
        looped = isSearchedNums[x]
        break
    isSearched[x] = True
    isSearchedNums[x] = n
    nums.append(x)
    n+=1
if (isSearched[0]):
    ans = X
    for i in range(min((N-1), len(nums))):
        ans += nums[i]

    print(ans)
else:
    ans = X
    al = 0
    d = len(nums) - looped
    for i in range(looped, len(nums)):
        al += nums[i]

    if N - 1 > len(nums):
        N -= len(nums)
        ans += sum(nums)
        ans += al * ((N-1) // d)
        for i in range(looped, ((N-1) % d) + looped):
            ans += nums[i]
    else:
        for i in range(i, N - 1):
            ans += nums[i]

    print(ans)

Submission status: Wrong Answer

Solution code:
li = list(map(int,input().split()))
n = li[0]
x = li[1]
m = li[2]
li2 = list()
li2.append(x)
z = x
tmp = -1
if(n==1):
    print(x)
    exit()

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

for i in range(n):
    z = (z*z)%m
    if(z == 0):
        break
    if(z in li2):
        tmp = li2.index(z)
        break
    else:
        li2.append(z)

if(tmp == -1):
    print(sum(li2))
else:
    nagasa = len(li2[tmp:])
    kekka = sum(li2)
    n = n - len(li2)
    q , mod = divmod(n,nagasa)
    kekka = kekka + sum(li2[tmp:])*q
    if(mod!=0):
        end = tmp+mod
        kekka = kekka + sum(li2[tmp:end])
    print(kekka)

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 = []

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)
        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
        if (N - i) % cnt - 2 == -1:
            res += ((N - i) // cnt) * res_loop
        elif (N - i) % cnt - 2 == -2:
            res += ((N - i) // cnt + 1) * res_loop
        else:
            res += ((N - i) // cnt) * res_loop + a_part[(N - i) % cnt - 2]
        break
    else:
        remainder_list.add(a)
        res += a

print(res)

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 = 0
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

loop = loop - cnt_init + 1

# 循環
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 += pow(now, 2, m)
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,math
try:sys.stdin,sys.stdout=open('input.txt','r'),open('out.txt','w')
except:pass
from sys import stdin,stdout;mod=int(1e9 + 7);from statistics import mode
from collections import *;from math import ceil,floor,inf,factorial,gcd,log2,sqrt,log
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
# print('{:.3f}'.format(1),round(1.123456789,4))
# sys.setrecursionlimit(500000)
def lcm(a,b): return (a*b)//gcd(a,b)
def setbits(n):return bin(n).count('1')
def resetbits(n):return bin(n).count('0')
def modinv(n,p):return pow(n,p-2,p)
def ncr(n,r):
    num,den=1,1;r=min(n,n-r)
    for i in range(r):num*=(n-i);den*=(i+1)
    return num//den
def ncr_p(n, r, p):
    num,den=1,1;r=min(r,n-r)
    for i in range(r):num = (num * (n - i)) % p ;den = (den * (i + 1)) % p
    return (num * modinv(den,p)) % p
def isPrime(num) :
    if num<=1:return False
    if num==2 or n==3:return True
    if (num % 2 == 0 or num % 3 == 0) :return False
    m = int(num**0.5)+1
    for i in range(5,m,6):
        if (num % i == 0 or num % (i + 2) == 0) :return False
    return True
def bin_search(s, low, high, val):
    while low <= high:
        mid = low + (high - low) // 2;
        if s[mid] == val:return mid
        elif s[mid] < val:low = mid + 1
        else:high = mid - 1
    return -1
def sumofdigit(num):
    count=0;
    while num : count+=num % 10;num //= 10;
    return count;
def inputmatrix():
    r,c=iia();mat=[0]*r;
    for i in range(r):mat[i]=iia();
    return r,c,mat;
def prefix_sum(n,s):
    for i in range(1,n):s[i]+=s[i-1]
    return s;
def binomial(n, k):
    if 0 <= k <= n:
        ntok = 1;ktok = 1
        for t in range(1, min(k, n - k) + 1):ntok *= n;ktok *= t;n -= 1
        return ntok // ktok
    else:return 0
def divisors(n):
    res = [];
    for i in range(1,ceil(sqrt(n))+1):
        if n%i == 0:
            if i==n//i:res.append(i)
            else:res.append(i);res.append(n//i)
    return res;
# code here
# print('start')
n,x,m= iia()
X=x
ans = x % m
temp = n%m
mull = n//m
# print(ans)
if mull==0:
    for i in range(1,n):
        prod = (x*x)%m
        ans+=prod
        x=prod
    print(ans)
else:
    rem = n % m
    for i in range(1,m):
        prod = (x*x)%m
        ans+=prod
        x=prod
    if mull > 0 and temp!=0 and x!=0:
        ans*=mull
    X=x
    for i in range(rem):
        prod = (X*X) % m
        ans += prod
        X = prod
    print(ans)
'''
6 2 1001
1000 2 16

'''

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
ans = x
aaa = 0
for i in range(min(n, m)-1):
    ans += (x**2) % m
    # print(ans, (x**2) % m)
    x = x**2
    x %= m
    if x == 0:
        aaa = 1
        # print(i)
        break
# print(492443256176507)
print(ans)

Submission status: Wrong Answer

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

for i in range(2,N+1):
  A_i = (A[-1]*A[-1])%M
  A.append(A_i)
  S += A_i
  if len(A) != len(set(A)):
    del A[-1]
    sum(A[A.index(A_i):])
    B = A[A.index(A_i):]
    S += ((N-len(A))//len(B))*sum(B) + sum(B[:(N-len(A))%len(B)])
    break

print(S)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,x,m = na()
from collections import defaultdict
d = defaultdict(int)
a = x
d[a] = 1
dp = [0,a]

for i in range(2,n+1):
    b = (a*a)%m
    if b in d:
        j = d[b]
        loo = n-j-1
        ll = i-j
        d = loo//ll
        e = loo%ll
        loosum = dp[i-1]-dp[j-1]
        print(loosum*d+dp[j+e-1])
        exit()
    d[b] = i
    dp.append(dp[-1]+b)
    a = b

print(dp[-1])

Submission status: Wrong Answer

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

a = x
count = 0
li = set()
while a%m*a%m not in li:
    
    a = a%m*a%m
    li.add(a)
l = len(li)
mul = (n-1)//l
rem = (n-1)%l
# print(mul, rem)
sum_ = sum(li)
count = sum_*mul + sum(sorted(list(li))[:rem]) + x
print(count)

Submission status: Wrong Answer

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

amari_count = [0]*m
amari_count[x] += 1
flag = -1
zero = False
#その時の余りと、答えの累積和
amari_list =[x]
sm = [x]
for i in range(min(n-1,m)):
    amari = (amari_list[i]**2)%m
    amari_list.append(amari)
    sm.append(sm[i]+amari)
    if amari_count[amari]>0:
        flag = amari
        idx = i
        break
    else:
        amari_count[amari] += 1
    if amari == 0:
        zero = True
        break

if flag < 0 or zero:
    ans = sm[-1]
else:
    ans = 0
    for i in range(len(sm)):
        if amari_list[i]==flag:
            if i > 0:
                left = i
                ans += sm[left-1]
                interval = idx-left+1
            else:
                left = 0
                interval = idx +1
            break

    loop_sum = sm[idx]-sm[left-1]
    loop_count = (n-left)//interval
    hamidashi = (n-left)%interval
    ans += loop_sum*loop_count
    if hamidashi >0:
        ans += sm[left+hamidashi-1]-sm[left+hamidashi-2]

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:
        flag=1
    if a[A]==1:
        flag==2
        break
    a[A]=1
    ans+=A
    Ans.append(A)
if flag==2:
    for i in range(N):
        if A==Ans[i]:
            break
    n=len(Ans)-i
    b=sum(Ans[:i])
    x=N//n
    y=N%n
    Sum=b+(ans-b)*(n)+sum(Ans[:y])
else:
    Sum=ans
print(Sum)

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 = []

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)
        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
        if (N - i) % cnt - 2 == -1:
            res += ((N - i) // cnt) * res_loop
        elif (N - i) % cnt - 2 == -2:
            res += ((N - i) // cnt) * res_loop + a
        else:
            res += ((N - i) // cnt) * res_loop + a_part[(N - i) % cnt - 2]
        break
    else:
        remainder_list.add(a)
        res += a

print(res)

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) / 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 pow(x, 2) >= m and not over_m:
        loop_lis = [tmp]
        over_m = True
        is_loop = True
    x = tmp
print(ans)

Submission status: Wrong Answer

Solution code:
N,X,M=list(map(int,input().split()))
boolean = [False] * (10**5+1)
sums = 0

rec=False
nums = [0]

Ai = X
index = 1
while(index <= N):
	sums += Ai
	print(sums)
	if(boolean[Ai]==True):
		if(nums[0]==Ai):
			looplength=len(nums)-1
			break
		if(rec == False):
			rec=True
			nums[0]=Ai
		nums.append(Ai)
	boolean[Ai]=True
	Ai = Ai**2 % M
	index+=1
	
if rec==True:
	a=0
	for x in range(1,looplength+1):
		a+=nums[x]
	b=0
	for x in range(1,(N-index)%looplength):
		b+=nums[x]

Submission status: Wrong Answer

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

d = defaultdict(int)
data = defaultdict(int)
d2 = []
d2.append(x)

cnt = 0
cnt += 1

for i in range(n):
    x = x**2 % m
    if d[x] == 1:
        st = data[x]
        cycle = cnt-st
        cycle_sum = sum(d2[st:])

        num_cycle = (n-st) // cycle
        amari = (n-st) % cycle

        # print(d2)
        # print(st, cycle, amari)

        print(num_cycle * cycle_sum + sum(d2[:st]) + sum(d2[st:st+amari]))
        sys.exit()
    else:
        d[x] = 1
        data[x] = cnt
        d2.append(x)
        cnt += 1
print(sum(d2))

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
g = x * 1
ans = x
arr = []
res = set([])
roop = (0, 0)
k = 0
for i in range(m + 1):
	tmp = x ** 2 % m
	if tmp in res:
		roop = (i + 1, tmp)
		break
	res.add(tmp)
	arr.append(tmp)
	ans += tmp
	x = tmp

for i, y in enumerate(arr):
	if y == roop[1]:
		k = i
		break

ini = sum(arr[:k])
mul = ans - ini - g
t, v = divmod(n - roop[0], roop[0])
# print(ans, ini, mul, t, v, roop)
print(ans + mul * t + sum(arr[k:k+v]))

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
smod=set()
lmod=[x]
smod.add(x)
for i in range(n):
    s=(x**2)%m
    if s in smod:
        break
    else:
        smod.add(s)
        lmod.append(s)
    x=s
sum=sum(lmod)
a=n//len(smod)
b=n%len(smod)
ans=sum*a
for i in lmod[:b]:
    ans+=i
print(ans)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
ans = x
cnt = [0] * m
loop = []
start = -1
for i in range(min(n, 3 * m)):
    x = (x * x) % m
    if cnt[x] == 1:
        loop.append(x)
        if start == -1:
            start = i
    cnt[x] += 1
for i in range(m):
    if cnt[i] > 0:
        ans +=  i
l = len(loop)
if l > 0:
    ans += sum(loop) * ((n-1-start) // l)
    ans += sum(loop[:(n-1-start)%l])
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 = []

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)
        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
        if (N - i) % cnt - 2 == -1:
            res += ((N - i) // cnt) * res_loop + a
        elif (N - i) % cnt - 2 == -2:
            res += ((N - i) // cnt) * res_loop
        else:
            res += ((N - i) // cnt) * res_loop + a_part[(N - i) % cnt - 2]
        break
    else:
        remainder_list.add(a)
        res += a

print(res)

Submission status: Wrong Answer

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

_next = ans = x
for i in range(2,n):
    _next = ((_next % m) ** 2) % m
    ans += _next

print(ans)

Submission status: Wrong Answer

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

a = X
ans = X
for i in range(N-1):
    ans += pow(X, 2*(i+1), M)

print(ans)

Submission status: Wrong Answer

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

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

def cal(x):
    return pow(x,2,M)

memo = set()
lis = []
while X not in memo:
    memo.add(X)
    lis.append(X)
    X = cal(X)
pos = lis.index(X)

print(((N-pos)//(len(memo)-pos)) * sum(lis[pos:]) + sum(lis[:N%(len(memo)-pos)]))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

A = [-1] * (10 ** 5)

i = 1
A[x] = i
d = deque()
d.append(x)
sum = []
sum.append(0)
sum.append(x)
while i < n:
    i += 1
    x = (x * x) % m
    if A[x] != -1:
        break
    A[x] = i
    sum.append(sum[-1] + x)

if i == n:
    print(sum[n])
    exit()
dis = i - A[x]
pre_i = A[x]
cnt = ((n + 1) - pre_i) // dis
div = (n + i - pre_i) % dis
ans = sum[pre_i - 1]
ans += (sum[i - 1] - sum[pre_i - 1]) * cnt
if div != 0:
    ans += (sum[pre_i + div - 1] - sum[pre_i - 1])
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 = 0
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

loop = loop - cnt_init + 1

# 循環
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)
# print(tmp, cnt)
# print(1369 - 6)
res += tmp * cnt

# 残り
nokori = (n - cnt_init) % loop
# print(cnt_init)
# print(loop)
# print(cnt)
# print(nokori)
if nokori == 0:
    print(res)
    exit()
now = last
res += last
for _ in range(nokori):
    res += pow(now, 2, m)
    now = pow(now, 2, m)

print(res)

Submission status: Wrong Answer

Solution code:
import sys,math
try:sys.stdin,sys.stdout=open('input.txt','r'),open('out.txt','w')
except:pass
from sys import stdin,stdout;mod=int(1e9 + 7);from statistics import mode
from collections import *;from math import ceil,floor,inf,factorial,gcd,log2,sqrt,log
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
# print('{:.3f}'.format(1),round(1.123456789,4))
# sys.setrecursionlimit(500000)
def lcm(a,b): return (a*b)//gcd(a,b)
def setbits(n):return bin(n).count('1')
def resetbits(n):return bin(n).count('0')
def modinv(n,p):return pow(n,p-2,p)
def ncr(n,r):
    num,den=1,1;r=min(n,n-r)
    for i in range(r):num*=(n-i);den*=(i+1)
    return num//den
def ncr_p(n, r, p):
    num,den=1,1;r=min(r,n-r)
    for i in range(r):num = (num * (n - i)) % p ;den = (den * (i + 1)) % p
    return (num * modinv(den,p)) % p
def isPrime(num) :
    if num<=1:return False
    if num==2 or n==3:return True
    if (num % 2 == 0 or num % 3 == 0) :return False
    m = int(num**0.5)+1
    for i in range(5,m,6):
        if (num % i == 0 or num % (i + 2) == 0) :return False
    return True
def bin_search(s, low, high, val):
    while low <= high:
        mid = low + (high - low) // 2;
        if s[mid] == val:return mid
        elif s[mid] < val:low = mid + 1
        else:high = mid - 1
    return -1
def sumofdigit(num):
    count=0;
    while num : count+=num % 10;num //= 10;
    return count;
def inputmatrix():
    r,c=iia();mat=[0]*r;
    for i in range(r):mat[i]=iia();
    return r,c,mat;
def prefix_sum(n,s):
    for i in range(1,n):s[i]+=s[i-1]
    return s;
def binomial(n, k):
    if 0 <= k <= n:
        ntok = 1;ktok = 1
        for t in range(1, min(k, n - k) + 1):ntok *= n;ktok *= t;n -= 1
        return ntok // ktok
    else:return 0
def divisors(n):
    res = [];
    for i in range(1,ceil(sqrt(n))+1):
        if n%i == 0:
            if i==n//i:res.append(i)
            else:res.append(i);res.append(n//i)
    return res;
# code here
# print('start')
n,x,m= iia()
X=x
ans = x % m
temp = n%m
mull = n//m
# print(ans)
if mull==0:
    for i in range(1,n):
        prod = (x*x)%m
        ans+=prod
        x=prod
    print(ans)
else:
    rem = n % m
    for i in range(1,m):
        prod = (x*x)%m
        ans+=prod
        x=prod
    if mull > 0 and temp!=0 and x!=0:
        ans*=mull
    # X=x
    for i in range(rem):
        prod = (X*X) % m
        ans += prod
        X = prod
    print(ans)
'''
6 2 1001
1000 2 16

'''

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 = []

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)
        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
        if (N - i) % cnt - 2 == -1:
            res += ((N - i) // cnt) * res_loop
        elif (N - i) % cnt - 2 == -2:
            res += ((N - i) // cnt) * res_loop
        else:
            res += ((N - i) // cnt) * res_loop + a_part[(N - i) % cnt - 2]
        break
    else:
        remainder_list.add(a)
        res += a

print(res)

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:
n,x,m=map(int,input().split())
smod=set()
lmod=[x]
smod.add(x)
for i in range(n):
    s=(x**2)%m
    if s in smod:
        break
    else:
        smod.add(s)
        lmod.append(s)
    x=s
sum=sum(lmod)
a=n//len(smod)
b=n%len(smod)
ans=sum*a
for i in lmod[:b]:
    ans+=i
print(smod)
print(ans)