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())
be = x % m
ans = be
memo = [[0,0] for i in range(m)]
am = [be]
memo[be-1] = [1,0]  #len-1
for i in range(n-1):
    be = be**2 % m
    if be == 0:
        break
    elif memo[be-1][0] == 1:
        kazu = memo[be-1][1]
        l = len(am) -  kazu
        syou = (n-i) // l
        amari = (n-i)%l
        sum = 0
        for k in range(kazu, len(am)):
            sum += am[k]
        ans = ans + syou*sum
        if amari > 0:
            for j in range(kazu,kazu + amari -1):
                ans += am[j]
        break
    else:
        ans += be
        am.append(be)
        memo[be-1][0] = 1
        memo[be-1][1] = len(am) -1
print(ans)

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
main=[x]
flag=0
a=x
result=0
def search(x):
    for i in range(len(main)):
        if main[i]==x:
            return i
    return -1
for i in range(n-1):
    a=a*a
    if a<m:
        main.append(a)
    elif search(a%m)>=0:
        a=a%m
        s=search(a%m)
        e=len(main)-1
        shuuki=0
        for j in range(s,e+1):
            shuuki+=main[j]
        #後何回かけるか
        if int((n-i)%(e-s+1))==0:
            for l in range(len(main)):
                result+=main[l]
            result+=int((n-i)/(e-s+1))*shuuki
        else:
            amari=(n-i)%(e-s+1)
            for l in range(len(main)):
                result+=main[l]
            result+=int((n-i-amari)/(e-s+1))*shuuki
            for l in range(s,s+amari):
                result+=main[l]
        flag=1
        break
    else:
        a=a%m
        main.append(a)
if flag==1:
    print(result)
else:
    for i in range(len(main)):
        result+=main[i]
    print(result)

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(1, N + 1):
    bef = pow(bef, 2, M)
    if bef in dic:
        posi = dic[bef]
        l = len(_sum) - posi
        plus = _sum[-1] - _sum[posi]
        count += plus * ((N - i - 1) // l)
        mod = ((N - i - 1) % l)
        count += _sum[posi + mod] - _sum[posi]
        break
    else:
        dic.setdefault(bef, i)
        _sum.append(bef + _sum[-1])
    count += bef

print(count)

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)
if a==0:
    print(sum(li)+x)
else:
    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:
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 -1) // length
        M2 = (N - pre -1) % 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())
main=[x]
flag=0
a=x
result=0
def search(x):
    for i in range(len(main)):
        if main[i]==x:
            return i
    return -1
for i in range(n-1):
    a=a*a
    if a<m:
        main.append(a)
    elif search(a%m)>=0:
        a=a%m
        s=search(a%m)
        e=len(main)-1
        shuuki=0
        for j in range(s,e+1):
            shuuki+=main[j]
        #後何回かけるか
        if int((n-i)%(e-s+1))==0:
            for l in range(len(main)):
                result+=main[l]
            result+=int((n-i)/(e-s+1))*shuuki
        else:
            amari=(n-i)%(e-s+1)
            for l in range(len(main)):
                result+=main[l]
            result+=int((n-i-amari)/(e-s+1))*shuuki
            for l in range(s,s+amari):
                result+=main[l]
        flag=1
        break
    else:
        a=a%m
        print(a)
        main.append(a)
if flag==1:
    print(result)
else:
    for i in range(len(main)):
        result+=main[i]
    print(result)

Submission status: Wrong Answer

Solution code:
N,X,M = map(int,input().split())
dps = [0,X%M]+[0 for i in range(N)]
rt = 0
for i in range(2,N+1):
  dps[i] = (dps[i-1]**2)%M
  rt+= dps[i]
print(rt)

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=map(int,input('').split(' '))
print(int((n*(n+1)*(2*n+1))/6)%m-int((x*(x+1)*(2*x+1))/6)%m)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

            break
start_idx = a.index(a[i])
loop_haba = i-start_idx
loop_sum = sum(a[start_idx:i])

if flag:
    print(sum(a[:n+1]))
else:
    ans = sum(a[:(start_idx)])

    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())
mod = m
amari = [-1]*m
a = x
cnt = 1
l = 0
r = 0
while 1:
    # print(a)
    if cnt == n:
        break
    
    if amari[a] != -1:
        l = amari[a]
        r = cnt
        # print(a,amari[a])
        break
    else:
        amari[a] = cnt
    cnt += 1
    a = ((a % m)**2) % m
    # if cnt > m:
    #     print("error")
    #     exit()
# print(l,r,amari)
ans = 0
if cnt == n:
    l = 0
    r = n

a = x
temp = 0
for i in range(l-1):
    ans += a
    a = (a**2) % mod
for i in range(r-l):
    temp += a
    a = (a**2) % mod
ans += temp * (n-l)//(r-l)
for i in range((n-l-1)%(r-l)):
    ans += a
    a = (a**2) % mod
print(ans)

Submission status: Wrong Answer

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


def ans(N):
  S = []
  pre_Ai = X
  A = pre_Ai
  break_num = 0
  for i in range(N-1):
    Ai= (pre_Ai**2)%M
    if pre_Ai**2>M:
      if Ai not in S:
        S.append(Ai)
      else:
        break_num = i
        A += sum(S)*len(S)
        break
    else:
      A += Ai
      pre_Ai = Ai 
      if Ai==0:
        break
  if break_num!=0:
    A += int((N-break_num)/len(S))*sum(S)
    for i in range((N-break_num)%len(S)):
      A += S[i]
  return A

print(ans(N))

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:
    app[a_i] = len(loop)
    loop.append(a_i)
# 答の計算
ans=x
if last < 0:
  ans += sum(loop)
else:
  # ループの端までは普通に足す
  ans += sum(loop[:app[last]])
  # ループの中を累計で足す
  ans += sum(loop[app[last]:]) * ((n-1) // (len(loop)-app[last]))
  # 余りを足す
  ans += sum(loop[app[last]:((n-1) % (len(loop)-app[last]))])
print(ans)
#print(*loop)

Submission status: Wrong Answer

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

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

a = x
a_set = {a}
a_array = [a]
a_index = 0
for i in range(10):
    a = f(a ** 2, m)
    if a in a_set:
        a_index = a_array.index(a)
        break
    a_set.add(a)
    a_array.append(a)

# print(a_array)
# print(a_index)
a_iter_array = a_array[a_index:]
# print(a_iter_array)
div, mod = divmod(n - a_index, len(a_set))
ans = sum(a_array[:a_index]) + sum(a_iter_array) * div + sum(a_iter_array[:mod])
print(ans)

Submission status: Wrong Answer

Solution code:
import math

N,X,M = map(int, input().split())
MAP = [0]*(M+1)
ans = 0
if N<M:
    for i in range(N):
        if (X%M!=0):
            X = X%M
            ans += X
            X = X**2
        else:
            break
else:
    for i in range(N):
        if (X%M!=0):
            X = X%M
            ans += X
            if MAP[X]==0:
                MAP[X]=1
            else:
                ans = (ans)*(N//(i-2))
                jmax = N-(N//(i-2))*(i)
                for j in range(jmax):
                    if (X%M!=0):
                        X = X%M
                        ans += X
                        X = X**2
                X=M
                break
            X = X**2
        else:
            break


print(ans)

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 A not in [z]:
        A.append(z)
    else:
        break

print(sum(A[:N]))

Submission status: Wrong Answer

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

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

ans = 0

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

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

    if aa == 0:
        break

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 = map(int, input().split())
ans = 0
cnt = 0
tmp = [-1] * M
tmp_v = [0] * M
while cnt < N:
    cnt += 1
    ans += X
    X *= X
    if X > M:
        X %= M
        if tmp[X] == -1:
            tmp[X] = cnt
            tmp_v[X] = ans
            continue
        else:
            ans += (ans - tmp_v[X]) * (N//(cnt - tmp[X]))
            cnt += (N//(cnt - tmp[X]))*(cnt - tmp[X])
    elif X == M:
        break
    elif X == M + 1:
        ans += N - cnt
        break
    
print(ans)

Submission status: Wrong Answer

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

def solve():
    N, X, M = list(map(int, input().split()))

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

    # A[i]の値は必ず mod Mの範囲に収まる
    # ということは循環する？
    # A[i]=0になったら、A[i+1]以降は必ず0
    A = [0]*(10**6+2)
    ruiseki = [0]*(10**6+2)
    A[0], ruiseki[1] = X, X
    total = X
    Aset = set([X])
    stop_i = 0
    is_zero = False
    for i in range(1, N):
        A[i] = f(pow(A[i-1], 2, M), M)
        ruiseki[i+1] = ruiseki[i] + A[i]
        if A[i] == 0:
            is_zero = True
            stop_i = i
            break
        if A[i] in Aset:
            stop_i = i
            break
        total += A[i]
        Aset.add(A[i])

    if stop_i == 0:
        print(total)
    elif is_zero:
        print(ruiseki[stop_i])
    else:
        ans = total*(N//stop_i)
        ans += ruiseki[(N%stop_i)+1]
        print(ans)


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import collections

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


def f(x):
    return x**2 % M


tuginoatai = [0] * (M)
motonoatai = [set() for _ in range(M)]

for i in range(M):
    tuginoatai[i] = f(i)
    motonoatai[tuginoatai[i]].add(i)

# 0 にいくか

to_zero = [False] * (M)

q = collections.deque()
q.append(0)
while q:
    x = q.popleft()
    for moto in motonoatai[x]:
        if to_zero[moto]:
            continue
        to_zero[moto] = True
        for y in motonoatai[moto]:
            q.append(y)

ans = 0
if to_zero[X]:
    x = X
    while x > 0:
        ans += x
        x = tuginoatai[x]
    print(ans)
else:
    # 一周分もとめる
    seen = set()
    x = X
    isshuunowa = 0
    isshuunoshuuki = 0
    while x not in seen:
        seen.add(x)
        isshuunowa += x
        isshuunoshuuki += 1
        sh = x
        x = tuginoatai[x]
    shuukinohajimari = x

    x = X
    while x != shuukinohajimari:
        ans += x
        isshuunowa -= x
        N -= 1
        isshuunoshuuki -= 1
        x = tuginoatai[x]

    shou, amari = divmod(N, isshuunoshuuki)
    ans = shou*isshuunowa
    for _ in range(amari):
        ans += x
        x = tuginoatai[x]
    print(ans)

Submission status: Wrong Answer

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

ans = 0
chck = 0
lst = [X]
if N == 1:
    print(X)

else:
    for i in range(N):
        X = (X**2)%M

        if i >= 2:
            if X == lst[2]:
                T = i-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:
nxm = [int(x) for x in input().split()]

n = nxm[0]
x = nxm[1]
m = nxm[2]

t = 0
 

ref = {}
sums = []
 
#[first find, second find]
 
i = 0
 
while i < n:

    if x in ref:
        if ref[x][1] == -1:
            ref[x][1] = i

            t += x
            x *= x
            x %= m

            sums.append(sums[len(sums)-1] + x)
            
        else:
            temp = ref[x][1] - ref[x][0]
            
            if temp == 0:
              break
              
            tempy = (n-i)//temp

            diff = sums[ref[x][1]] - sums[ref[x][0]-1]

            t += tempy*diff
            i += tempy*temp
    else:
        ref[x] = [i,-1]

        if i == 0:
            sums.append(x)
        else:
            sums.append(sums[len(sums)-1] + x)

        t += x
        x *= x
        x %= m

print(t)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N,X,M = map(int,input().split())
A = X%M
Ans = A
Modset = set()
Modset.add(A)
sig = 0
N -= 1
for i in range(10**7):
    A = pow(A,2,M)
    Ans += A
    if A ==0:
        break
    if A not in Modset:
        Modset.add(A)
        N -= 1
    else:
        Ans -= A
        sig = 1
        break
print(N,Ans)
if sig == 1:
    S = A
    B = A
    rep = 0
    for i in range(10**6):
        B = pow(B,2,M)
        rep += 1
        if A== B:
            break
        else:
            S += B
    Rep = N//rep
    Ans += Rep*S
    N -= Rep*rep
    if N != 0:
        Ans += A
        N -= 1
        for i in range(10**6):
            if N == 0:
                break
            Ans += pow(A,2,M)
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
        ans += sum(loop[:M2-1])

    print(ans)

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:
n, x, m = map(int,input().split())
li = [0]*(m+1)

cnt1 = 0
cnt2 = 0
ans1 = x
ans2 = 0
a = x
flag = 0

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

    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:
    print(ans1+ans2*(n-cnt1)//cnt2+((n-cnt1)%cnt2))


    # print((n-cnt1)%cnt2)

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[j-1+y] - 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:
# -*- 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(sum(lis[:pos]) + ((N-pos)//(len(memo)-pos)) * sum(lis[pos:]) + sum(lis[:(N-pos)%(len(memo)-pos)]))

Submission status: Wrong Answer

Solution code:
n,x,m= list(map(int, input().split()))
listm=[x]
before=x
for i in range(2,n+1):
    now=before**2%m
    if now in listm:
        iti=listm.index(now)
        print(sum(listm)+sum(listm[iti:])*((n-i+1)//(i-iti))+sum(listm[iti:((n-i+1)%(i-iti))+iti+1]))
        exit()
    listm.append(now)
    before=now
print(sum(listm))

Submission status: Wrong Answer

Solution code:

def euclid(a:int,b:int)->(int,int):
    #return x,y s.t ax + by = gcd(a,b)
    #a > b >= 0
    if b == 0:
        return 1,0
    x,y = euclid(b,a%b)
    return y,x - y*(a // b)

def inverse(a:int,mod:int)->int:
    #gcd(p,b) == 1
    if mod > a:
        n,x = euclid(mod,a)
    else:
        x,n = euclid(a,mod)
    return x

def devide_mod(a:int,b:int,mod:int)->int:
    #a // b
    x = inverse(b,mod)
    return  (a*x)%mod


def pow(x, n,m):
    ans = 1
    while n:
        if n % 2:
            ans = ans*x%m
        x = (x**2)%m
        n >>= 1
    return ans

def main():
    n,x,m = map(int,input().split())
    ans = devide_mod(x - pow(x,2*n,m), (1 - x**2),m)
    print(ans)
    return

if __name__ == "__main__":
    main()

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 or 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:
#!/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)
            break
    if X == 0:
        print(0)
    elif nx == -1:
        print(sum(list_x))
    else:
        repeat = list_x[nx:]
        print(sum(list_x[:nx]) + (N // len(list_x[nx:])) * sum(repeat) + sum(repeat[:(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())
A = [X]
sumA = 0

for n in range(N):
    sumA += A[n]
    A.append(A[n] ** 2 % M)
    if (A[-1] in A[0:-1]) and n != N-1:
        print(sumA)
        a_start = A[0:-1].index(A[-1])
        A_len = len(A)-1

        a = A[a_start:-1]
        a_ite = len(a)
        a_sum = sum(a)

        A_ite = (N-A_len) // a_ite
        A_ext = (N-A_len) % a_ite+1+a_start

        sumA += a_ite*a_sum + sum(A[a_start:A_ext])
        break

print(sumA)

Submission status: Wrong Answer

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n, x, m = MI()
    a = x
    flag = [False]*(m+1)
    t = 0
    s = []
    idx = 0
    for _ in range(m+1):
        if flag[a]:
            idx = s.index(a)
            break
        flag[a] = True
        s.append(a)
        t += a
        a = (a*a) % m
        if a == 0:
            print(t)
            sys.exit()
    ans = sum(s[0:idx])
    ans += sum(s[idx:])*((n-idx)//len(s))
    ans += sum(s[idx:idx+(n-idx)%len(s)+1])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

chk = [0 for i in range(m)]
a = x
s = x
c = 0
ary = [x]
flg = False
while True:
  if c == n:
    break
  x = (x**2)%m
  s += x
  c += 1
  if chk[x]:
    flg = True
    break
  ary.append(x)
  chk[x] = c
if flg == False:
  print (s)
  exit()
cyc = ary[chk[x]:]

ss = ary[:chk[x]]
tot = sum(ss) + sum(cyc)*((n-len(ss))//len(cyc)) + sum(cyc[:((n-len(ss))%len(cyc))])
print (tot)

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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:
			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):
		ret += nx
		nx = (nx*nx)%m
	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:
N, X, M = map(int, input().split())

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

pre = set()
pre.add(X)
cnt = 1
tmp = X
while cnt < N:
    X = tmp * tmp
    tmp = f(X, M)
    if tmp in pre: break
    pre.add(tmp)
    cnt += 1

if tmp == 0:
    print(sum(pre))
elif tmp == 1:
    print(sum(pre) + N - cnt)
else:
    ans = sum(pre) * (N//cnt)
    left = N - (N//cnt) * cnt
    for i in range(left):
        X = f(X, M)
        ans += X
        X = X * X
    print(ans)

Submission status: Wrong Answer

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

idx = defaultdict()
idx[X] = 0

iii = -1

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

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

Submission status: Wrong Answer

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

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

ans = 0

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

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

    if aa == 0:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int,input().split())
if (m == 1):
    print(x)
elif (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:
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)
        a_tmp = a
        while True:
            remainder_loop.append(a)
            res_loop += a
            a = a ** 2 % M
            a_part.append(a_part[-1] + a)
            cnt += 1
            if a == rem_trig or cnt + i >= N:
                break
        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_tmp
        else:
            res += ((N - i) // cnt) * res_loop + a_part[(N - i) % cnt - 2]
        break
    else:
        remainder_list.add(a)
        res += a

print(res)