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())
# 一定回数を経ると循環するので最後にかければよい
loop=list()
app = [0]*m
last = -1
a_i = x
while 1+len(loop) < n:
  a_i = (a_i**2)%m
  if app[a_i]:
    # もしくはloopの端にきたらloop開始
    last = a_i
    break
  else:
    loop.append(a_i)
    app[a_i] = len(loop)
# 答の計算
ans=x
if last < 0:
  ans += sum(loop)
else:
  # ループの端までは普通に足す
  ans += sum(loop[:app[last]-1])
  # ループの中を累計で足す
  ans += sum(loop[app[last]-1:]) * ((n-1) // (len(loop)-app[last]+1))
  # 余りを足す
  ans += sum(loop[app[last]-1:((n-1) % (len(loop)-app[last]+1))])
print(ans)
#print(*loop)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from math import floor

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

ls = [X]
enc = [0] * M
enc[X] = 1

count = 1

while count < N:
  X *= X
  X = X % M
  count += 1
  if enc[X] == 0:
    enc[X] += 1
    ls.append(X)
  else:
    ls.append(X)
    break

if count == N:
  print(sum(ls))
else:
  first = ls.index(X)
  interval = count - first - 1
  
  out = sum(ls[:first]) + floor((N - first) / interval) * sum(ls[first:count - 1])
  if (N - first - 1) % interval != 0:
    out += sum(ls[first: first + (N - first) % interval])

  print(out)

Submission status: Wrong Answer

Solution code:
def main():
    N, X, M = map(int, input().split())
    A = [X % M]
    setA = set(A)

    while True:
        a = (A[-1] ** 2) % M
        if a in setA:
            break
        A.append(a)
        setA.add(a)

    pre = A.index(a)
    ans = 0
    loop = A[pre:]
    length = len(loop)
    if N - 1 < pre:
        ans += sum(A[:N-1])
    else:
        M1 = (N - pre) // length
        M2 = (N - pre) % length
        ans += sum(A[:pre])
        ans += sum(loop) * M1
        ans += sum(loop[:M2])

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, X, M = map(int,input().split())
import sys
ans = 0
ls = [X%M] + [-1]*(M+1)
for i in range(N):
    a = ls[i]
    ls[i+1] = pow(a,2,M)
    if i+1 < N and ls[i+1] in ls[:i]:
        b = ls[i+1]
        L = ls.index(b)
        R = i
        len_roop = R - L + 1
        p = (N - L) // len_roop
        q = (N - L) % len_roop
        break
else:
    for i in range(N):
        ans += ls[i]
    print(ans)   
    sys.exit()
    
sum_roop = 0        
for i in range(L, R+1):
    sum_roop += ls[i]
    
sum_edge = 0
for i in range(L, L+q):
    sum_edge += ls[i] 
    
for i in range(L):
    ans += ls[i]
else:
    ans += sum_roop * p + sum_edge        
    
print(ls)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, X: int, M: int):
    list_x = [X]
    nx = -1
    for _ in range(N-1):
        m = X % M
        X = (m * m) % M
        if X not in list_x:
            list_x.append(X)
        else:
            nx = list_x.index(X)
            # print("Break")
            break
    
    # print(list_x)
    # print(nx)
    # print(sum(list_x[(N % len(list_x)):]))
    if nx == -1:
        print(sum(list_x))
    else:
        # gggg = len(len(list_x[nx:]))
        repeat = list_x[nx:]
        # print(repeat)
        print(sum(list_x[:nx]) + (N // len(list_x[nx:])) * sum(repeat) + sum(repeat[0:(N-nx) % len(repeat)]))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(N, X, M)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

sum = X
Ai  = X
I = 0
for i in range (N-1):
  Ai = Ai**2 % M
  sum += Ai
  if Ai == X:
    I = i
    break

if I != 0:
  sum = sum * N / I
print (sum)

Submission status: Wrong Answer

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

ans = 0
chck = 0
lst = [X]
for i in range(N-1):
    X = (X**2)%M

    if X in lst:
        l = lst.index(X)
        T = i-l+1
        chck = 1
        break

    lst.append(X)

    if X == 0:
        break


if chck:
    p = N//T
    q = N%T
    ans = sum(lst[2:])*p + sum(lst[:q])

else:
    ans =sum(lst)

print(ans)

Submission status: Wrong Answer

Solution code:
N,X,M=map(int,input().split())
table=list(range(M))
for i in range(M):
    table[i]=(table[i]*table[i])%M
start=X%M
rireki=list()
rireki.append(start)
for j in range(1,N):
    if table[start] in rireki:
        break
    else:
        rireki.append(table[start])
        start=table[start]
nn=len(table)
rep=N//nn
nokori=N-rep*nn
if 0 in rireki:
    goukei=sum(rireki)
else:
    goukei=rep*sum(rireki)+sum(rireki[:nokori])
print(goukei)

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(x==0):
    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:
from collections import defaultdict
n, x, m = list(map(int, input().split()))
dp = [False]*(m+1)
a = [0]*(m+1)
d = defaultdict(lambda: set())

for i in range(1, m+1):
    if i == 1:
        a[i] = x
        dp[x] = True
    else:
        a[i] = a[i-1]**2 % m
        if not dp[a[i]]:
            d[a[i-1]] = a[i]
            dp[a[i]] = True
        else:
            startv = a[i]
            break
start_idx = a.index(a[i])
loop_haba = i-start_idx
loop_sum = sum(a[start_idx:i])
# print(a)
# print(start_idx, loop_sum, loop_haba)
if n <= (start_idx+loop_haba-1):
    print(sum(a[:n+1]))
else:
    ans = sum(a[:(start_idx+1)])
    ans += ((n-start_idx)//loop_haba)*loop_sum
    ans += sum(a[start_idx: start_idx+((n-start_idx) % loop_haba)+1])
    print(ans)

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
a = X
i = 0
cnt = 0
li = [-1]*M
x = 0

if N > M:
    for i in range(M):
        if li[a] != -1:
            break
        else:
            li[a] = i
            cnt += a
            a = pow(a, 2, M)
            x += 1
    # print(cnt)
    # print(x, li[a])
    if x-li[a] > 1:
        s = 0
        for i in range(li[a], x):
            s += li[i]
        cnt += (N-x)//(x-li[a]-1)*s
        for i in range((N-x) % (x-li[a]-1)+1):
            cnt += li.index(i+1)
    print(cnt)
else:
    for i in range(M):
        if li[a] != -1:
            break
        else:
            li[a] = i
            cnt += a
            a = pow(a, 2, M)
    print(cnt)

Submission status: Wrong Answer

Solution code:
from math import floor

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

ls = [X]
enc = [0] * M
enc[X] = 1

count = 1

while count < N:
  X *= X
  X = X % M
  count += 1
  if enc[X] == 0:
    enc[X] += 1
    ls.append(X)
  else:
    ls.append(X)
    print(count)
    break

if count == N:
  print(sum(ls))
else:
  print(ls[count -1])
  first = ls.index(X)
  print(first)
  interval = count - first - 1
  
  out = sum(ls[:first]) + floor((N - first) / interval) * sum(ls[first:count - 1])
  if (N - first - 1) % interval != 0:
    out += sum(ls[first: first + (N - first) % interval])

  print(out)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n, x, m = 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)
now = last
res += last
for _ in range(nokori - 1):
    res += pow(now, 2, m)
    now = pow(now, 2, m)

print(res)

Submission status: Wrong Answer

Solution code:


def main():
    n, x, m = map(int, input().split())
    l = [x]
    ltot = [x]

    flg = 0
    tot = x
    a = x
    for i in range(n):
        a = a ** 2 % m
        if a in set(l):
            for j in range(len(l)):
                if l[j] == a:
                    l2 = l[j:]
                    z = (n - j) // len(l2) - 1
                    y = (n - j) % len(l2)
                    tot += (ltot[y-1] - ltot[j-1]) + (ltot[-1] - ltot[j-1]) * z
                    # tot += sum(l2[:y]) + sum(l2) * z
                    flg = 1
                    break
        if flg:
            break
        tot += a
        l.append(a)
        ltot.append(tot)

    print(tot)


main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
a=input('').split()
a=list(map(int,a))
N=a[0]
X=a[1]
M=a[2]
t=0
b=X
S=0

while t<N:
  X=((X)**2)%M
  b=b+X
  t=t+1

print(b)

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+10):
        prod = (X*X) % m
        ans += prod
        X = prod
    print(ans)
'''
6 2 1001
1000 2 16

'''

Submission status: Wrong Answer

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


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

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
a = x
s = 0
h = []
h.append(a)
i = 0
fl = 0
while i < n:
    s += a
    a = (a*a) % m
    if a == 0:
      break
    i += 1
    if a in h and fl == 0:
      fl = 1
      po = h.index(a)
      ss = 0
      for j in range(po):
        ss += h[j]
      s2 = s - ss
      f = n // (i - po)
      s2 *= f
      s = s2 + ss
      i2 = i - po
      i2 *= f
      i = i2 + po
    else:
      h.append(a)
print(s)

Submission status: Wrong Answer

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

lis=[0]*m

ans=x
ai=x
lis[ai]=[1,ans]
flg=0

for i in range(2,n+1):
    ai=(ai**2)%m
    if lis[ai]!=0:
        start=lis[ai][0]
        goal=i-1
        span=goal-start+1
        sumspan=ans-lis[ai][1]+ai
        flg=1
        break
    ans+=ai
    lis[ai]=[i,ans]

if flg:
    times=(n-goal)//span
    last=(n-goal)%span
    ans+=sumspan*times
    print(last)
    #print(sumspan*times)
    if last==1:
        ans+=ai
    for i in range(0,last-1):
        ans+=ai
        #print(i)
        ai=(ai**2)%m
        if i == last-2:
            ans+=ai
    print(ans)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, X, M = map(int, input().split())
    A = [X % M]
    setA = set(A)

    while True:
        a = (A[-1] ** 2) % M
        if a in setA:
            break
        A.append(a)
        setA.add(a)

    pre = A.index(a)
    ans = 0
    loop = A[pre:]
    length = len(loop)
    if N - 1 < pre:
        ans += sum(A[:N-1])
    else:
        M1 = (N - pre) // length
        M2 = (N - pre) % length
        ans += sum(A[:pre])
        ans += sum(loop) * M1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, X, M = map(int,input().split())
dp = [X]
now = X
while True:
    if now ** 2 % M in dp:
        break
    dp.append(now ** 2 % M)
    now **= 2
#print(dp)
sum_val = sum(dp)
if N <= len(dp):
    print(sum(dp[:N]))
else:
    if dp[-1] == 0:
        print(sum(dp))
    else:
        print(sum_val * (N // len(dp)) + sum(dp[:N % M]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,X,M=map(int,input().split())
mod={X}
ans=0
for _ in range(M):
    X=X**2%M
    mod.add(X)
x=N%len(mod)
if x!=0:
    ans+=X
    for _ in range(x-1):
        ans+=X**2%M
ans+=sum(mod)*(N//len(mod))
if 0 in mod:
    ans=sum(mod)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from sys import stdin
def I():
    return stdin.readline().rstrip()
def MI():
    return map(int,stdin.readline().rstrip().split())
def LI():
    return list(map(int,stdin.readline().rstrip().split()))
#main part
n,x,m=MI()
if n<=m:
    sum=0
    a=x
    for _ in range(n):
        sum+=a
        a=(a**2)%m
    print(sum)
else:
    #zero check
    b=x
    while b<m:
        b=b**2
        if b==m:
            s=[]
            for i in range(n):
                s.append(x)
                x=(x**2)%m
                if x==0:
                    break
            print(sum(s))
            sys.exit()
    s=[]
    a=x
    for _ in range(m):
        s.append(a)
        a=(a**2)%m
    sho=n//m
    rest=n%m
    sum_=sum(s)
    ans=0
    ans+=sho*sum_
    for i in range(rest):
        ans+=s[i]
    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
        res += ((N - i) // cnt) * res_loop + a_part[max(0, (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, open(0).read().split())
if N == 1:
    print(X)
elif M == 1:
    print(0)
else:
    A = []
    A.append(X)
    B = []
    for i in range(N-1):
        if pow(A[-1],2) < M:
            A.append(pow(A[-1],2))
        else:
            B.append(pow(A[-1],2,M))
            b = set(B)
            for i in range(N-len(A)):
                temp = pow(B[-1],2,M)
                if temp not in b:
                    B.append(temp)
                    b.add(temp)
                else:
                    break
            else:
                continue
            break
    if len(B) == 0:
        print(sum(A))
    else:
        As = sum(A)
        Bs = sum(B)
        t1 = N - len(A)
        dm = divmod(t1,len(B))
        print(As+Bs*dm[0]+sum(B[:dm[1]]))

Submission status: Wrong Answer

Solution code:
def main():
    N, X, M = map(int, input().split())
    mod_set = set([X])
    mod_list = [X]
    zero_flag = False
    repeat_idx = 0
    for _ in range(M+100):
        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:
N, X, M = [int(i) for i in input().split()]
ans = X
A = X
l = [X]
r = [X]

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

Submission status: Wrong Answer

Solution code:
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()

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 = [int(i) for i in input().split()]
ans = X
A = X
l = [X]
r = [X]

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

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
A = X
jut = 1
if X == 0:
    jut = 0
cntt = 1
while(jut == 1):
    A = A**2
    cntt += 1 
    if A > M:
        jut = 2
    elif A == M:
        jut = 3

sk = False
sklp = []
lpkey = -1
if jut == 2:
    ans = X
    lpsize = -1
    lpsum = -1
    tans = 0
    for i in range(N-1):
        X = X**2 % M
        ans += X
        if i == cntt-1:
            lpkey = X
            tans = ans
            sk = True
        if sk:
            sklp.append(X)
        if X == lpkey:
            lpsize = i+1 - cntt
            lpsum = ans - tans
            break
    if lpsize <= 0:
        am1 = 1
        am2 = 0
    else:
        am1 = (N-cntt)//lpsize
        am2 = (N-cntt)%lpsize
    am3 = 0
    for i in range(am2):
        am3 += sklp[i]
    
    print(tans + lpsum*am1 + am3)

if jut == 3:
    ans = X
    for _ in range(cntt):
        X = X**2 % M
        ans += X
    print(ans)

if jut == 0:
    print(0)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n, x, m = map(int, input().split())
seen = [-1] * m
is_done = True
ans = 0
for i in range(n):
    if i == 0:
        val = x
    else:
        val = val * val % m
    if seen[val] != -1:
        loop_len = i - seen[val]
        loop_val = val
        is_done = False
        cnt = i
        break
    else:
        seen[val] = i
        ans += val
if is_done:
    print(ans)
    exit()
n -= (cnt + 1)

val = loop_val
loop_sum = 0
for i in range(loop_len):
    val = val * val % m
    loop_sum += val
ans += (n // loop_len) * loop_sum
for i in range(n % loop_len):
    val = val * val % m
    ans += val

print(ans)

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
d = []
d.append(x)
flag = True
for j in range(n):
  if (x*x)%m == 0:
    ans = sum(d)
    print(ans)
    flag = False
    break
  if (x*x)%m in d:
    l = len(d)
    ans = sum(d) * (n//l)
    for i in range(n%l):
      ans += d[i]
    print(ans)
    flag = False
    break
  x = (x*x)%m
  d.append(x)
if flag:
  ans = sum(d)
  print(ans)

Submission status: Wrong Answer

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

count = X
bef = X
_sum = [X]
dic = {X: 0}

for i in range(N):
    bef = pow(bef, 2, M)
    if bef in dic:
        posi = dic[bef]
        l = len(_sum) - posi
        plus = _sum[-1] - _sum[posi - 1]
        count += plus * ((N - i - 1) // l)
        mod = ((N - i - 1) % l)
        count += _sum[posi - 1 + mod] - _sum[posi - 1]
        break
    else:
        dic.setdefault(bef, i + 1)
        _sum.append(bef + _sum[-1])
    count += bef

print(count)

Submission status: Wrong Answer

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

Submission status: 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
                
                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]

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
        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())
l=[0 for i in range(m)]
ans=0
y=[]
i=1
flag=0
ys=n
while i<n:
    if flag==0:
        ans+=x
    l[x]+=1
    x=x*x%m
    i+=1
    if l[x]==2 and flag==0:
        flag=1
        ys=i
    if flag:
        if l[x]==3:
            break
        y.append(x)
if len(y):
    p,pp=divmod(n-ys,len(y))
    print(ans+p*sum(y)+sum(y[:pp+1]))
    #print(ans,p*sum(y),sum(y[:pp+1]))
else:
    print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N, X, M = 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 cnt + i >= N:
            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())
l=[0 for i in range(m)]
ans=0
y=[]
i=1
flag=0
ys=n
while i<n:
    if flag==0:
        ans+=x
    l[x]+=1
    x=x*x%m
    i+=1
    if l[x]==2 and flag==0:
        flag=1
        ys=i
    if flag:
        if l[x]==3:
            break
        y.append(x)
if len(y):
    p,pp=divmod(n-ys,len(y))
    print(ans+p*sum(y)+sum(y[:pp+1]))
    print(ans,p*sum(y),sum(y[:pp+1]))
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
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//(len(memo)-pos) * sum(lis[pos:]) + sum(lis[:N%(len(memo)-pos)]))

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
d = []
d.append(x)
flag = True
for j in range(n):
  if (x*x)%m == 0:
    ans = sum(d)
    print(ans)
    flag = False
    break
  if (x*x)%m in d:
    l = len(d)
    ans = sum(d) * (n//l)
    for i in range(n%l):
      ans += d[i]
    print(ans)
    flag = False
    break
  x = (x*x)%m
  d.append(x)
if flag:
  ans = sum(d)
  print(ans)