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

Solution (Python):

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

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    if ai!=x:
        for i in range(icnt+1):
            asum0+=ai0
            ai0=(ai0*ai0)%m
            icnt0+=1
            if ai0==ai:
                break
    icntk=icnt-icnt0
    if icntk==0:

        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
        ans=asum0+x*(n-icnt0)
        print(ans)       
    else:

        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
        ans=asum0+asumk*nk+asumr    
        print(ans)

Solution (Python):
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] 
sum_p = 0 
X = [False] * m 
for _ in range(mn):
    if X[x]:
        pre_len = P.index(x)
        cyc_len = len(P) - pre_len
        nxt_len = (n - pre_len) % cyc_len
        pre = sum(P[:pre_len])
        cyc = (sum_p - pre) * ((n - pre_len) // cyc_len)
        nxt = sum(P[pre_len: pre_len + nxt_len])
        print(pre + cyc + nxt)
        exit()
    X[x] = True
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)

Solution (Python):
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] 
sum_p = 0 
X = [False] * m 
for _ in range(mn):
    if X[x]:
        pre_len = P.index(x)
        cyc_len = len(P) - pre_len
        nxt_len = (n - pre_len) % cyc_len
        cyc = sum(P[pre_len:]) * ((n - pre_len) // cyc_len)
        remain = sum(P[:pre_len + nxt_len])
        print(cyc + remain)
        exit()
    X[x] = True
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)

Solution (Python):
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] 
sum_p = 0 
X = [False] * m 
for _ in range(mn):
    if X[x]:
        pre_len = P.index(x)
        cyc_len = len(P) - pre_len
        nxt_len = (n - pre_len) % cyc_len
        cyc_num = (n - pre_len) // cyc_len
        cyc = sum(P[pre_len:])
        remain = sum(P[:pre_len + nxt_len])
        print(cyc * cyc_num + remain)
        exit()
    X[x] = True
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)

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

mn = min(n, m)
P = [] 
sum_p = 0 
X = [False] * m 

for _ in range(mn):
    if X[x]: break
    X[x]  = True
    P.append(x)
    sum_p += x
    x = x*x % m

if len(P) >= mn:
    print(sum_p)
    exit()

pre_len = P.index(x)
cyc_len = len(P) - pre_len
nxt_len = (n - pre_len) % cyc_len

cyc_num = (n - pre_len) // cyc_len

cyc = sum(P[pre_len:])
remain = sum(P[:pre_len + nxt_len])

print(cyc * cyc_num + remain)

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

logn = (10**10).bit_length()
doubling = []
sumd = []
for _ in range(logn):
  tmpd = [-1] * m
  doubling.append(tmpd)
  tmps = [0] * m
  sumd.append(tmps)

for i in range(m):
  doubling[0][i] = i * i % m
  sumd[0][i] = i

for i in range(1,logn):
  for j in range(m):
    doubling[i][j] = doubling[i-1][doubling[i-1][j]]
    sumd[i][j] = sumd[i-1][j] + sumd[i-1][doubling[i-1][j]]

now = x
pos = 0
result = 0
while n:
  if n & 1:
    result += sumd[pos][now]
    now = doubling[pos][now]
  n = n >> 1
  pos += 1

print(result)

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

mn = min(n, m)
P = [] 
sum_p = 0 
X = [False] * m

for i in range(mn):
    if X[x]: break
    X[x]  = True
    P.append(x)
    sum_p += x
    x = x*x % m

if len(P) >= mn:
    print(sum_p)
    exit()

pre_len = P.index(x)
cyc_len = len(P) - pre_len
nxt_len = (n - pre_len) % cyc_len

cyc_num = (n - pre_len) // cyc_len

pre = sum(P[:pre_len])
cyc = sum_p - pre
nxt = sum(P[pre_len: pre_len + nxt_len])

print(pre + cyc * cyc_num + nxt)

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

a = X
path = [a]  
done = set([a])  
while True:
    na = pow(a, 2, M)
    if na in done:
        s = path.index(na)  
        break
    else:
        path.append(na)
        done.add(na)
        a = na

if N < s + 1:  
    ans = sum(path[:N])
else:
    rest = N - s  
    x, y = divmod(rest, len(path) - s)  

    ans = sum(path[:s])  
    ans += sum(path[s:]) * x  
    ans += sum(path[s: s + y])  
print(ans)

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

Solution (Python):

import sys
import collections as cl


def II(): 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()
    rep = []
    rep_set = set([])
    i = 1

    rep.append(X)
    rep_set.add(X)
    flag = True

    while flag and i < N:
        x = rep[i-1] ** 2 % M
        if x in rep_set:
            rep.append(x)
            break
        rep.append(x)
        rep_set.add(x)
        i += 1

    if i == N:
        print(sum(rep))
    else:
        l = rep.index(rep[-1])
        rep_leng = i - l
        rep_sum = sum(rep[l:i])
        ans = 0
        ans += sum(rep[:l])
        N -= l
        rep_num = N // rep_leng
        rep_amari = N % rep_leng
        ans += rep_sum * rep_num
        ans += sum(rep[l:l+rep_amari])
        print(ans)


main()

Solution (Python):
import math
import sys
pin=sys.stdin.readline

def main():
  N,X,M=map(int,pin().split())
  A=X
  d=[X]
  su=X
  for i in range(N-1):
    A=(A**2)%M
    if A in d:
      t=d.index(A)
      T=N-i-1
      d=d[t:]
      l=len(d)
      su+=sum(d)*(T//l)
      T=T%(T//l)
      su+=sum(d[:T])
      print(su)
      return
    d.append(A)
    su+=A
  print(su)
  return
main()

Solution (Python):
n,x,m = map(int,input().split())
k_1 = set()
k_2 = set()
tmp = list()
loop_number = 0
loop_sum = 0
while x not in k_1:
	k_1.add(x)
	x = x*x%m
while x not in k_2:
	k_2.add(x)
	tmp.append(x)
	loop_number+=1
	loop_sum+=x 
	x = x*x%m
ans = 0
k_1 = list(k_1)
for i in range(len(k_1)):
	ans +=  k_1[i]
ans = ans + loop_sum * ((n-len(k_1))//loop_number)
for i in range((n-len(k_1))%loop_number):
	ans += tmp[i]
print(ans)

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

a = X
path = [a]
done = set([a])
while True:
    na = pow(a, 2, M)
    if na in done:
        s = path.index(na)  
        break
    else:
        path.append(na)
        done.add(na)
        a = na

if N < s + 1:  
    ans = sum(path[:N])
else:
    rest = N - s  
    x, y = divmod(rest, len(path) - s)  

    ans = sum(path[:s])  
    ans += sum(path[s:]) * x  
    ans += sum(path[s: s + y])  
print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline


def main():
    N, X, M = map(int, readline().split())

    P = N.bit_length()
    pos = [[0] * M for _ in range(P)]
    value = [[0] * M for _ in range(P)]

    for r in range(M):
        pos[0][r] = r * r % M
        value[0][r] = r

    for p in range(P - 1):
        for r in range(M):
            pos[p + 1][r] = pos[p][pos[p][r]]
            value[p + 1][r] = value[p][r] + value[p][pos[p][r]]

    ans = 0
    cur = X
    for p in range(P):
        if N & (1 << p):
            ans += value[p][cur]
            cur = pos[p][cur]

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, X, M = map(int, readline().split())

    P = N.bit_length()
    pos = [[0] * M for _ in range(P)]
    value = [[0] * M for _ in range(P)]

    for r in range(M):
        pos[0][r] = r * r % M
        value[0][r] = r

    for p in range(P - 1):
        for r in range(M):
            pos[p + 1][r] = pos[p][pos[p][r]]
            value[p + 1][r] = value[p][r] + value[p][pos[p][r]]

    ans = 0
    cur = X
    for p in range(P):
        if N & (1 << p):
            ans += value[p][cur]
            cur = pos[p][cur]

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, X, M = map(int, readline().split())

    n = 1
    P = 1
    while n < N:
        n *= 2
        P += 1

    pos = [[0] * M for _ in range(P)]
    value = [[0] * M for _ in range(P)]

    for r in range(M):
        pos[0][r] = r * r % M
        value[0][r] = r

    for p in range(P - 1):
        for r in range(M):
            pos[p + 1][r] = pos[p][pos[p][r]]
            value[p + 1][r] = value[p][r] + value[p][pos[p][r]]

    ans = 0
    cur = X % M
    for p in range(P):
        if N & (1 << p):
            ans += value[p][cur]
            cur = pos[p][cur]

    print(ans)
    return


if __name__ == '__main__':
    main()

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

mn = min(n, m)
S = set()
A = []
sum_9 = 0 

for _ in range(mn):
    if x in S: break
    S.add(x)
    A.append(x)
    sum_9 += x
    x = x*x % m

if len(A) >= mn:
    print(sum_9)
    exit()

pre_len = A.index(x)
cyc_len = len(A) - pre_len
nxt_len = (n - pre_len) % cyc_len

cyc_num = (n - pre_len) // cyc_len

pre = sum(A[:pre_len])
cyc = sum_9 - pre
nxt = sum(A[pre_len: pre_len + nxt_len])

print(pre + cyc * cyc_num + nxt)

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

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

mn = min(n, m)
S = set()
A = []
a = x
sum_9 = 0 

for _ in range(mn):
    if a in S: break
    S.add(a)
    A.append(a)
    sum_9 += a
    a = a*a % m

if len(A) >= mn:
    print(sum_9)
    exit()

pre_len = A.index(a)
cyc_len = len(A) - pre_len
btm_len = (n - pre_len) % cyc_len

cyc_num = (n - pre_len) // cyc_len

pre = sum(A[:pre_len])
cyc = sum_9 - pre
btm = sum(A[pre_len: pre_len + btm_len])

print(pre + cyc * cyc_num + btm)

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

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

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

mn = min(n, m)
S = set()
A = []
a = x
sum_9 = 0 

for _ in range(mn):
    if a in S: break
    S.add(a)
    A.append(a)
    sum_9 += a
    a = a*a % m
    if a == 0:
        print(sum_9)
        exit()

if len(A) >= mn:
    print(sum_9)
    exit()

st_len = A.index(a)
cyc_len = len(A) - st_len
ed_len = (n - st_len) % cyc_len

cyc_num = (n - st_len) // cyc_len

pre = sum(A[:st_len])
cyc = sum_9 - pre
btm = sum(A[st_len: st_len + ed_len])

print(pre + cyc * cyc_num + btm)

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

is_appear = [-1]*M
a = []
_len = 0
while is_appear[X] == -1:
    a.append(X)
    is_appear[X] = _len
    _len += 1
    X = X*X % M

loop_len = _len-is_appear[X]
loop_total = 0
for i in range(is_appear[X], _len):
    loop_total += a[i]

ans = 0
if N <= _len:
    for i in range(N):
        ans += a[i]
    
    print(ans)
else:
    for i in range(is_appear[X]):
        ans += a[i]
        N -= 1
    
    ans += loop_total * (N // loop_len)
    
    for i in range(N%loop_len):
        ans += a[is_appear[X]+i]
    
    print(ans)

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

mn = min(n, m)
S = set()
A = []
a = x
ans = 0

for i in range(mn):
    if a in S: break
    S.add(a)
    A.append(a)
    ans += a
    a = a*a%m
    if a == 0:
        print(ans)
        exit()

if len(A) >= mn:
    print(ans)
    exit()

st_len = 0
while st_len < len(A) and a != A[st_len]: st_len += 1
st = sum(A[:st_len])
cyc_sum = sum(A[st_len:])
cyc_len = len(A) - st_len
cyc_num = (n - st_len) // cyc_len
cyc = cyc_sum * cyc_num
ed_len = (n - st_len) % cyc_len
ed = sum(A[st_len:][:ed_len])
print(st + cyc + ed)

Solution (Python):
n, x, m = map(int, input().split())
mn = min(n, m)
S = set()
A = []
a = x
ans = 0
for i in range(mn):
    if a in S: break
    S.add(a)
    A.append(a)
    ans += a
    a = a*a%m
    if a == 0:
        print(ans)
        exit()




if len(A) < mn:
    st_len = 0
    while st_len < len(A) and a != A[st_len]: st_len += 1
    st = sum(A[:st_len])
    cyc_sum = sum(A[st_len:])
    cyc_len = len(A) - st_len
    cyc_num = (n - st_len) // cyc_len
    
    cyc = cyc_sum * cyc_num
    ed_len = (n - st_len) % cyc_len
    ed = sum(A[st_len:][:ed_len])
    print(st + cyc + ed)
else:
    print(ans)

Solution (Python):
from math import log2
n,x,m = map(int, input().split())

logn = int(log2(n))+1
db = [[0]*m for _ in range(logn)]
dbs = [[0]*m for _ in range(logn)]

for i in range(m):
    db[0][i] = (i**2)%m
    dbs[0][i] = (i**2)%m

for i in range(logn-1):
    for j in range(m):
        db[i+1][j] = db[i][db[i][j]]
        dbs[i+1][j] = dbs[i][db[i][j]] + dbs[i][j]


ans = x
now = x
for i in range(logn):
    if (n-1)&(1<<i) > 0:
        ans += dbs[i][now]
        now = db[i][now]

print(ans)

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

roop_count = last_count-first_count

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

Solution (Python):
import sys

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

if N == 1: 
  print(X)
  sys.exit()

ans = 0
ans += X - (X%M) 
X %= M 

def fun(x): 
  return (x * x) % M

appear_set = {X} 


i_0 = 1 
x = X 
sum_0 = x 



while fun(x) not in appear_set: 
  x = fun(x) 
  appear_set.add(x) 
  sum_0 += x 
  i_0 += 1   
  
  if i_0 == N: 
    print(ans + sum_0)
    sys.exit()




ans += sum_0
N -= i_0








x = fun(x) 
appear_set_2 = {x} 
sum_1 = x        
sum_list = [0,x] 
i_1 = 1 



while fun(x) not in appear_set_2:
  x = fun(x)
  appear_set_2.add(x)
  sum_1 += x 
  sum_list.append(sum_1) 
  i_1 += 1
  


ans += sum_1 * (N // i_1) + sum_list[(N % i_1)]

print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N, X, M = MI()
    S = list([X])
    num = X
    for i in range(N-1):
        num = (num**2) % M
        if not num in S:
            S.append(num)
        else:
            break

    len_s = len(S)
    if len_s == N:
        print(sum(S))
    else:
        index_s = S.index(num)
        
        num1 = index_s
        sum1 = sum(S[0:index_s])
        
        
        num2 = len_s - index_s
        sum2 = sum(S)-sum1
        
        
        num3 = (N-num1) // num2
        sum3 = sum2 * num3
        
        
        num4 = (N-num1) % num2
        sum4 = sum(S[index_s:index_s+num4])
        
        ans = sum1+sum3+sum4
        print(ans)
    
    
if __name__ == "__main__":
    main()

Solution (Python):
n,x,mod=map(int,input().split())
d=[-1]*mod
ans=0
syu=0
al=[]
for i in range(n):
    if d[x]!=-1:
        en=i
        syu=i-d[x]    
        break
    ans+=x
    al.append(x)
    d[x]=i
    x=x*x%mod   
if syu==0:
    print(ans)
    exit()
ans+=((n-en)//syu)*sum(al[d[x]:en])
for i in range((n-en)%syu):
    ans+=x%mod
    x=x*x%mod
print(ans)

Solution (Python):
N,x,M=map(int,input().split())
k=x
L=list()
c=dict()
for i in range(M):
  if i==N:
    print(sum(L))
    exit()
  if x==0:
    print(sum(L))
    exit()
  L.append(x)
  x=(x*x)%M
  if x in c:
    q=x
    break
  c[x]=1
moto=sum(L)
N-=len(L)
for i in range(len(L)):
  if L[i]==q:
    roop=list(L[i:])
L=roop
a=len(L)
if N%a==0:
  print(moto+(sum(L)*(N//a)))
else:
  s=N//a
  t=N%a
  ans=sum(L)*s
  ans+=sum(roop[:t])
  print(moto+ans)

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

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

c = l - id[x]
s=0

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

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

Solution (Python):
def main():
    n, x, m = map(int, input().split())
    idx = [-1] * (m + 1)  
    res = []  

    for i in range(1, m + 3):  
        if idx[x] == -1:  
            idx[x] = i
            res.append(x)
            x = (x ** 2) % m
        else:  
            len_loop = i - idx[x]
            len_head = idx[x] - 1
            break

    if n <= len_head + len_loop:  
        print(sum(res[:n]))
    else:
        ans = sum(res[:len_head])  

        loop_count = (n - len_head) // len_loop
        ans += loop_count * sum(res[len_head:])  

        len_tail = (n - len_head) % len_loop
        ans += sum(res[len_head: len_head + len_tail])  

        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

N, X, M = map(int, sys.stdin.readline().split())

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

a = []
a.append(X)

exists = set()
exists.add(X)
ans = a[0]
for i in range(1, N):
    tmp = f(a[i-1], M)
    if tmp in exists:
        start = a.index(tmp)
        
        break
    ans += tmp
    a.append(tmp)
    exists.add(tmp)
else:
    
    print(ans)
    sys.exit()



 
before_score = sum(a[:start])


loop = a[start:]

loop_score = sum(loop)

loop_n = len(loop)
N -= start
res_n = N % loop_n
print(before_score + loop_score * (N // loop_n) + sum(loop[:res_n]))

Solution (Python):
def main():
    n, x, m = map(int, input().split())
    idx = [-1] * (m + 1)  
    res = []  

    for i in range(1, m + 3):  
        if idx[x] == -1:  
            idx[x] = i
            res.append(x)
        else:  
            len_loop = i - idx[x]
            len_head = idx[x] - 1
            break
        x = (x ** 2) % m

    if n <= len_head + len_loop:  
        print(sum(res[:n]))
    else:
        ans = sum(res[:len_head])  
        ans += (n - len_head) // len_loop * sum(res[len_head:])  
        ans += sum(res[len_head: len_head + (n - len_head) %
                       len_loop])  
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys



from copy import *
from bisect import *	

from math import gcd,ceil,sqrt
from itertools import permutations as prm,product
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 

if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
di=[[-1,0],[1,0],[0,1],[0,-1]]
def inc(d,c,x=1):
	d[c]=d[c]+x if c in d else x
def bo(i):
	return ord(i)-ord('A')	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def comp(a,b):
	if(a>b):
		return 2
	return 2 if a==b else 0		
def gi():	
	return [xx for xx in input().split()]
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j):
	return 0<=i<n and 0<=j<m and a[i][j]!="."
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)

t=1
mod=998244353



while t>0:
	t-=1
	n,k,m=mi()
	vis={}
	cycle=[]
	i=ans=0
	while k not in vis:
		cycle.append(k)
		vis[k]=i
		i+=1
		ans+=k
		if i==n:
			print(ans)
			exit(0)
		k=(k**2)%m
		if k in vis:
			cycle=cycle[vis[k]:]
			n-=i

	s=sum(cycle)
	p=n%len(cycle)
	z=len(cycle)
	print(ans+(n//z)*s+sum(cycle[:p]))

Solution (Python):
n, x, m = list(map(int, input().split()))
a = [x]
start = -1
end = -1
check = [0]*m
path = -1
loop = 0

for i in range(1, n):
    ans = (a[i-1]**2) % m
    p = check[ans]
    if p != 0:
        if start == -1:
            start = i
            path = ans
        if p == 1:
            end = i
    if p >= 3:
        break
    check[ans] += 1
    a.append(ans)


if start == -1 or end == -1:
    print(sum(a))
else:
    lenght = end-start+1
    loop, mod = divmod(n-start, lenght)
    ans = sum(a[:start])+sum(a[start:end+1])*loop + sum(a[start:start+mod])
    print(ans)

Solution (Python):

import sys
input = sys.stdin.readline
N, X, M = map(int,input().split())
A = [0 for _ in range(M+1)]
A[1] = X
S = [0 if i == 0 else X for i in range(M+1)]
first = [-1 for i in range(M+1)]
if X <= M:
	first[X] = 1

n = 1
a = X
l,r = -1, -1
while True:
	if n == N:
		break
	a2 = (a*a) % M
	if a2 == 0:
		print(S[n])
		exit()
	if first[a2] > 0:
		l = first[a2]
		r = n
		break
	first[a2] = n + 1
	A[n+1] = a2
	S[n+1] = S[n] + a2
	a = a2
	n += 1

if n == N:
	print(S[N])
	exit()
t = r - l + 1
loop = (N-l+1) // t
rest = (N-l+1) % t
print(S[l-1] + loop * (S[r] - S[l-1]) + S[l + rest - 1] - S[l-1])

Solution (Python):
N, X, M = map(int, input().split())
 
def next_f(a):
    return a * a % M
 
visited = [None] * M
sum_at_visit = [None] * M
loop_done = False
 
time = 1
ans = 0
x = X
while time <= N:
    if not loop_done and visited[x] is not None:
        
        loop_len = time - visited[x]
        loop_sum = ans + x - sum_at_visit[x]
        loops = (N-loop_len-time) // loop_len
        time += loop_len * loops
        ans += loop_sum * loops
        loop_done = True
    ans += x
    visited[x] = time
    sum_at_visit[x] = ans
    time += 1
    x = next_f(x)
print(ans)

Solution (Python):
N,X,M = map(int,input().split())
id = [-1] * M
lis = []
tot = 0
le = 0
while id[X] == -1:
    id[X] = le
    le += 1
    lis.append(X)
    tot += X
    X = (X**2) % M

c = le - id[X]
sm = 0
for i in range(id[X],le):
    sm += lis[i]
if (N <= le):
    ans = 0
    for i in range(N):
        ans += lis[i]
    print(ans)
    exit()

ans = tot
N -= le
ans += N // c * sm
N %= c
for i in range(id[X],id[X]+N):
    ans += lis[i]
print(ans)

Solution (Python):
n, x, m = map(int, input().split())
ans = x
L = [0 for i in range(m+1)]
L[x] = 1

A = [x]
t = True
count = 2
while t:
    x = (x*x)%m
    if L[x] != 0:
        start = L[x]
        t = False
    else:
        L[x] = count
        count += 1
        A.append(x)

if A[-1] == 0:
    if len(A) - 1 > n:
        ans = sum(A[:n])
    else:
        ans = sum(A)

elif len(A) >= n:
    ans = sum(A[:n])
else:
    length = len(A)-start+1
    ans = sum(A[:(start-1)])
    t = (n-start+1) // length 
    s = (n-start+1) % length
    ans += sum(A[(start-1):])*t 
    ans += sum(A[start-1:(start-1+s)])
print(ans)

Solution (Python):
N,X,M = [int(a) for a in input().split()]
amari = [0]*M
i = 1
A = X
amari[A] = i
l = [X]
ichi = i
while i<=M:
    i += 1
    A = A**2 % M
    if amari[A]: i += M
    else:
        amari[A] = i
        l.append(A)
    if i==N: i = M+1
else:
    if i>M+1: ni = i-M - amari[A]
    else: ni = 0



ichi = len(l) - ni

if ni:
    ni_times, san = divmod((N - ichi), ni)
    
    print(sum(l[:ichi]) + 
          sum(l[ichi:])*ni_times + 
          sum(l[ichi:ichi+san]))
else:
    
    print(sum(l))

Solution (Python):
N, X, M = map(int, input().split())
if X == 0:
    print(0)
    exit()
tx = X % M
tl = []
ts = set()
ttl = []
for i in range(N):
    tl.append(tx)
    ts.add(tx)
    tx = pow(tx, 2, M)
    if tx in ts:
        ttl = tl[tl.index(tx):]
        break
ans = sum(tl)
if len(ttl)>0:
    d, m = divmod(N-len(tl), len(ttl))
    ans += sum(ttl)*d+sum(ttl[:m])
print(ans)

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

I = [-1] * M
A = []
total = 0
while (I[X] == -1):
    A.append(X)
    I[X] = len(A)
    total += X
    X = (X * X) % M






c = len(A) - I[X] + 1
s = sum(A[I[X] - 1:])

ans = 0
if N < len(A):
    ans += sum(A[:N])
else:
    ans += total
    N -= len(A)
    ans += s * (N // c)
    N %= c
    ans += sum(A[I[X] - 1:I[X] - 1 + N])
print(ans)

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

visited = [False] * M

tmp = X
total_sum = X
visited[tmp] = True

total_len = 1
while True:
    tmp = (tmp ** 2) % M
    if visited[tmp]:
        loop_start_num = tmp
        break
    total_sum += tmp
    visited[tmp] = True
    total_len += 1

path_len = 0
tmp = X
path_sum = 0

while True:
    if tmp == loop_start_num:
        break
    path_len += 1
    path_sum += tmp
    tmp = (tmp ** 2) % M

loop_len = total_len - path_len
loop_sum = total_sum - path_sum


result = 0
if N <= path_len:
    tmp = X
    for i in range(N):
        result += X
        tmp = (tmp ** 2) % M
    print(result)
else:
    result = path_sum
    N -= path_len
    loops_count = N // loop_len
    loop_rem = N % loop_len
    result += loop_sum * loops_count
    tmp = loop_start_num
    for i in range(loop_rem):
        result += tmp
        tmp = (tmp ** 2) % M
    print(result)

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

y=x
A=[]
A.append(y)
cnt=1
su=x

for i in range(m):
    y=(y**2)%m
    cnt+=1
    if y in A:
        break
    else:
        A.append(y)
        su+=y

c=A.index(y) 
d=cnt-(c+1)  

e=sum(A[:c]) 



f=sum(A[c:c+(n-c)%d])
    

g=su-e
h=g*((n-c)//d)

print(e+h+f)

Solution (Python):

import sys
inputlinevec = sys.stdin.readline().strip().split(' ')
n = int(inputlinevec[0])
x = int(inputlinevec[1])
m = int(inputlinevec[2])

sum_res = x
crcle_dict = dict()
crcle_list = list()
crcle_idx = 0
pre_a = x

for idx in range(1, n):
    
    
    
    this_a = (pre_a * pre_a) % m
    pre_a = this_a
    
    if this_a not in crcle_dict:
        crcle_dict[this_a] = 1
        crcle_list.append(this_a)
        sum_res = sum_res + this_a
    else:
        crcle_step = len(crcle_list) - crcle_list.index(this_a)
        remain_crcle = int((n - idx) / crcle_step)
        remain_crcle_tail = int((n - idx) % crcle_step)
        
        crcle_sum = 0
        crcle_sum_tail = 0
        for a_item in crcle_list[crcle_list.index(this_a):]:
            crcle_sum = crcle_sum + a_item
            remain_crcle_tail = remain_crcle_tail - 1
            if remain_crcle_tail == 0:
                crcle_sum_tail = crcle_sum
        sum_res = sum_res + (remain_crcle * crcle_sum) + crcle_sum_tail
        break
    
print(sum_res)

Solution (Python):
from collections import defaultdict
it = lambda: list(map(int, input().strip().split()))


def solve():
    N, X, M = it()
    if N == 1: return X % M

    cur = 0
    cnt = 0
    value = defaultdict(int)
    history = defaultdict(int)
    for i in range(N):
        if X in history: break
        value[X] = cur
        history[X] = i
        cnt += 1
        cur += X
        X = X * X % M
        
    loop = cur - value[X]
    period = i - history[X]
    freq, rem = divmod(N - cnt, period)
    cur += freq * loop
    for i in range(rem):
        cur += X
        X = X * X % M
    return cur


if __name__ == '__main__':
    print(solve())

Solution (Python):
n,x,m=map(int,input().split())
r=[]
s=set()
ans=x
a=x
for i in range(n-1):
    b=a*a%m
    if b in s:
        j = r.index(b)
        N = n-1-i
        T = i-j
        S = sum(r[j:])
        ans += N//T*S
        N %= T
        ans += sum(r[j:j+N])
        break
    else:
        ans+=b
        s.add(b)
        r.append(b)
        a=b
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

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

nex = [(i ** 2) % M for i in range(M)]
cum = [i for i in range(M)]

ans = 0
while N:
  if N & 1:
    ans += cum[X]
    X = nex[X]
  cum = [cum[i] + cum[nex[i]] for i in range(M)]
  nex = [nex[nex[i]] for i in range(M)]
  N >>= 1

print(ans)

Solution (Python):
def solve():
    N, X, M = map(int,input().split())
    past_a = {X}
    A = [X]
    ans = prev = X
    for i in range(1, min(M,N)):
        next_a = prev ** 2 % M
        if next_a in past_a:
            loop_start = A.index(next_a)
            loop_end = i
            loop_size = loop_end - loop_start
            loop_elem = A[loop_start:loop_end]

            rest_n = N-i
            ans += rest_n // loop_size * sum(loop_elem)
            ans += sum(loop_elem[:rest_n%loop_size])
            break

        ans += next_a
        past_a.add(next_a)
        A.append(next_a)
        prev = next_a
    
    print(ans)
    
if __name__ == '__main__':
    solve()

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

a = []
check = [-1] * m
i = 0
while check[x] == -1:
  a.append(x)
  check[x] = i
  x = x * x % m
  i += 1
if n <= i:
  print(sum(a[:n]))
else:
  print(
    sum(a[:check[x]])
    + (n - check[x]) // (i - check[x]) * sum(a[check[x]:])
    + sum(a[check[x] : check[x] + (n - check[x]) % (i - check[x])]))