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 = list(map(int, input().split()))




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


A = [X]
s = {X}
i = 0
while True:
    A_next = f(A[-1], M)
    if A_next in s:
        i = A.index(A_next)
        break
    else:
        A.append(A_next)
        s.add(A_next)

loop_length = len(A) - i
loop_cnt = (N - i) // loop_length
loop_res = (N - i) % loop_length
ans = sum(A[:i]) + loop_cnt * sum(A[i:]) + sum(A[i: i + loop_res])


print(ans)

Solution (Python):

"""
Created on Sat Sep 19 22:03:19 2020

@author: liang
"""

N, X, M = map(int,input().split())
mod_set = {X}
mod_lis = [X]
A = [0]*(10**6+1)
A[0] = X
flag = False

"""
【for文のループ用の変数を、
　●for文外で使ったり
 ●for文内で書き換えたり
 してはいけない】
 (理由)
●for文外で使うとき、for文に入らない入力値の場合
　　【未定義】
　となり、エラーが出る。　
 ⇒　【for文外で定義済み】の他の変数に保存する
●for文内で書き換えると、ループが壊れてしまう
 ⇒　一旦別の変数に保存し、その変数を書き換える

【整数の切り捨て演算は計算順序に注意】
*ans += T_sum * (N-j)//T
　⇒T_sum * (N-j)　を Tで割っているのでダメ
<対策 1: 切り捨て演算は括弧で囲む>
 ⇒ans += T_sum * ( (N-j)//T )
<対策 2: 切り捨て演算は予め計算しておく>
 ●divmod(a,b) => return (a//b,a%b)

"""
l = 1
for i in range(1,min(10**6,N)):
    l = i
    tmp = A[i-1]**2%M
    if tmp in mod_set:
        flag = True
        break
    A[i] = tmp
    mod_set.add(tmp)
    mod_lis.append(tmp)

if flag:
    j = mod_lis.index(tmp)
else:
    j = l
T = l - j
ans = 0
if T != 0:  
    
    ans += sum(mod_lis[:j])
    T_sum = sum(mod_lis[j:])
    q, r = divmod(N-j,T)
    ans += T_sum * q
    
    T_lis = mod_lis[j:]   
    ans += sum(T_lis[:r])
else:
    
    ans = sum(mod_lis)
   



print(ans)

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

dp = [None]*mod

a = x
arr = [a]

for i in range(n-1):
  if dp[a] is not None:
    idx = arr.index(a)
    sum_early = sum(arr[:idx])
    cycle = i - idx
    sum_repeat = sum(arr[idx:-1])
    repeat_num = (n - idx) // cycle
    end_num = (n - idx) % cycle
    sum_end = sum(arr[idx:idx+end_num])
    ans = sum_early + sum_repeat*repeat_num + sum_end
    print(ans)
    exit()
  tmp = pow(a, 2, mod)
  dp[a] = tmp
  a = tmp
  arr.append(a)

print(sum(arr))

Solution (Python):

"""
Created on Sat Sep 19 22:03:19 2020

@author: liang
"""

N, X, M = map(int,input().split())
mod_set = {X}
mod_lis = [X]
A = [0]*(10**6+1)
A[0] = X
flag = False

"""
【for文のループ用の変数を、
　●for文外で使ったり
 ●for文内で書き換えたり
 してはいけない】
 (理由)
●for文外で使うとき、for文に入らない入力値の場合
　　【未定義】
　となり、エラーが出る。　
 ⇒　【for文外で定義済み】の他の変数に保存する
●for文内で書き換えると、ループが壊れてしまう
 ⇒　一旦別の変数に保存し、その変数を書き換える

【整数の切り捨て演算は計算順序に注意】
*ans += T_sum * (N-j)//T
　⇒T_sum * (N-j)　を Tで割っているのでダメ
<対策 1: 切り捨て演算は括弧で囲む>
 ⇒ans += T_sum * ( (N-j)//T )
<対策 2: 切り捨て演算は予め計算しておく>
 ●divmod(a,b) => return (a//b,a%b)

"""
l = 1
for i in range(1,min(10**6,N)):
    l = i
    tmp = A[i-1]**2%M
    if tmp in mod_set:
        flag = True
        break
    A[i] = tmp
    mod_set.add(tmp)
    mod_lis.append(tmp)

if flag:
    j = mod_lis.index(tmp)
else:
    j = l
T = l - j
ans = 0
if T != 0:  
    
    ans += sum(mod_lis[:j])
    T_sum = sum(mod_lis[j:])
    q, r = divmod(N-j,T)
    ans += T_sum * q
    
    T_lis = mod_lis[j:]   
    ans += sum(T_lis[:r])
else:
    
    ans = sum(mod_lis)
   



print(ans)

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1


def main():
    n,x,m = map(int,ipt().split())
    rps = [x]
    ln = [-1]*m
    ln[x] = 0
    nn = x
    rs = 0
    rg = n
    for i in range(1,n):
        nn = (nn**2)%m
        if ln[nn] == -1:
            ln[nn] = i
            rps.append(nn)
        else:
            rs = ln[nn]
            rg = i
            break
    ans = sum(rps[:rs:])
    smsg = sum(rps[rs:rg:])
    rpl = rg-rs
    ans += (n-rs)//rpl*smsg
    ans += sum(rps[rs:rs+(n-rs)%rpl:])

    print(ans)

    return None

if __name__ == '__main__':
    main()

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

S = {X : 1}

path = [X]

cnt = 1
ans = X
a = X
for i in range(2, N + 1):
    a = a * a % M
    if a in S:
        cnt = i - S[a]
        break
    S[a] = i

    ans += a
    path.append(a)

pre_len = S[a] - 1

Q, R = divmod(N - pre_len - 1, len(path) - pre_len)

pre = sum(path[:pre_len])
cycle = sum(path) - pre

ans = a
for _ in range(R):
    a = a * a % M
    ans += a

print(pre + Q * cycle + ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, X, M = NMI()
    A = []
    A_ID = {}
    break_flag = False
    start = 0
    end = N
    for i in range(M):
        if i == 0:
            A.append(X)
            A_ID[X] = 0
        else:
            x = A[-1]**2 % M
            if x not in A_ID:
                A.append(x)
                A_ID[x] = i
            else:
                A.append(x)
                start = A_ID[x]
                end = i
                break_flag = True
            if break_flag:
                break

    if N < start+1:
        print(sum(A[:N]))
        exit()

    ans = sum(A[:start])
    lp = sum(A[start:end])
    gap = end - start
    lp_n = (N - start) // gap
    rem = (N - start) % gap
    ans += lp * lp_n + sum(A[start: start + rem])
    print(ans)




if __name__ == "__main__":
    main()

Solution (Python):
import sys
from math import ceil as C, floor as F, sqrt, gcd as G
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data) 

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

n, x, m = I()

seen = [x]
ans = x
for i in range(1, n):
    now = seen[-1]
    next = (now * now) % m

    if next not in seen:
        seen.append(next)
        ans += next
    else:
        loop = seen[seen.index(next):]
        count = len(loop)
        total = sum(loop)
        remain = n - i
        
        q, r = remain // count, remain % count
        ans += q * total
        ans += sum(loop[:r])
        break
        
print(ans)

Solution (Python):
n, x, m = map(int, input().split())
lis = set()
loop_lis = []
cnt = 0
while x not in lis:
    cnt += 1
    lis.add(x)
    loop_lis.append(x)
    x = pow(x, 2) % m
    if cnt == n:
        print(sum(lis))
        exit()

start = loop_lis.index(x)
length = len(loop_lis) - start
loop_sum = sum(loop_lis[start:])
before = sum(loop_lis[:start])
loop = loop_sum * ((n - start) // length)
remain = sum(loop_lis[start : (start + (n - start) % length)])

print(before + loop + remain)

Solution (Python):

"""
Created on Sat Sep 19 22:03:19 2020

@author: liang
"""

N, X, M = map(int,input().split())
mod_set = {X}
mod_lis = [X]
A = [0]*(10**6+1)
A[0] = X
flag = False

i = 1
for i in range(1,min(10**6,N)):
    tmp = A[i-1]**2%M
    if tmp in mod_set:
        flag = True
        break
    A[i] = tmp
    mod_set.add(tmp)
    mod_lis.append(tmp)

if flag:
    j = mod_lis.index(tmp)
else:
    j = i
T = i - j
ans = 0
if T != 0:  
    
    ans += sum(mod_lis[:j])
    T_sum = sum(mod_lis[j:])
    """
    【切り捨て演算は必ず()をつけて先に計算】
    """
    ans += T_sum * ((N-j)//T)
    
    T_lis = mod_lis[j:i]   
    ans += sum(T_lis[:(N-j)%T])
else:
    
    ans = sum(mod_lis)
   



print(ans)

Solution (Python):
N, X, M = map(int, input().split())
N -= 1
L = 1
while 1 << L <= N:
    L += 1
table = [[None] * M for _ in range(L)]
for i in range(M):
    x = i * i % M
    table[0][i] = (x, x)
for i in range(1, L):
    for j in range(M):
        k, s = table[i-1][j]
        l, t = table[i-1][k]
        table[i][j] = (l, s + t)
ans = X
for i in range(L)[::-1]:
    if (1 << i) <= N:
        j, s = table[i][X]
        ans += s
        N -= (1 << i)
        X = j
print(ans)

Solution (Python):

"""
Created on Sat Sep 19 22:58:03 2020

@author: liang
"""

N,X,M=map(int,input().split())
a = X
hist = [a]
indices = [-1]*M
indices[a] = 0
flag=0
for i in range(1,min(10**6,N)):
  a = a**2 % M
  if indices[a] != -1:
    idx = indices[a]
    flag=1
    break
  hist.append(a)
  indices[a] = i
  
if flag==0:
  print(sum(hist))
  exit()
  
cycle = hist[idx:]
margin = hist[:idx]
q,r = divmod((N-len(margin)),len(cycle))
ans = 0
ans += sum(margin)
ans += sum(cycle)*q

ans += sum(cycle[:r])


print(ans)

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

t_loop = [X]

f_loop = [X]

memo = {X:1}

s_loop = []
while True:
    new_val = t_loop[-1]**2%M
    t_loop.append(new_val)
    if new_val not in memo:
        memo[new_val] = 1
        f_loop.append(new_val)
    else:
        memo[new_val] += 1
        if memo[new_val] == 3:
            break
        else:
            s_loop.append(new_val)

ans = 0
if N <= len(f_loop):
    ans += sum(f_loop[:N])
else:
    ans += sum(f_loop)
    shou = (N-len(f_loop))//len(s_loop)
    amari = (N-len(f_loop))%len(s_loop)
    ans += shou*sum(s_loop)
    ans += sum(s_loop[:amari])
    
print(ans)

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

ans = 0

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

    print(ans)

Solution (Python):

def resolve():
  N, X, M = map(int, input().split(" "))
  checked = [False] * M
  val = X
  ans = 0
  val_list = []

  base = M
  for i in range(N):
    if checked[val] != False:
      loop_start_index = checked[val]
      loop_vals = val_list[loop_start_index:]
      loop_val = sum(loop_vals)
      loop_length = len(val_list[loop_start_index:])
      
      if loop_length != 0:
        ans += ((N - i) // loop_length) * loop_val

        for i in range(((N - i) % loop_length)):
          ans += loop_vals[i]
      break
    ans += val
    checked[val] = i
    val_list.append(val)

    val*=val
    if val >= base:
      val %= base


  print(ans)

if __name__ == "__main__":
  resolve()

Solution (Python):
N,X,M = map(int,input().split())
t_loop = [X]
f_loop = [X]
f_memo = {X:1}
s_loop = []
while True:
    new_val = t_loop[-1]**2%M
    t_loop.append(new_val)
    if new_val not in f_memo:
        f_memo[new_val] = 1
        f_loop.append(new_val)
    else:
        f_memo[new_val] += 1
        if f_memo[new_val] == 3:
            break
        else:
            s_loop.append(new_val)

ans = 0
if N <= len(f_loop):
    ans += sum(f_loop[:N])
else:
    ans += sum(f_loop)
    shou = (N-len(f_loop))//len(s_loop)
    amari = (N-len(f_loop))%len(s_loop)
    ans += shou*sum(s_loop)
    ans += sum(s_loop[:amari])
    
print(ans)

Solution (Python):
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(1,n):
    aa = pow(aa,2,m)
    if aa in aset:
        offset = alist.index(aa)
        loop = alist[offset:i]
        nloop, tail = divmod(n-offset, len(loop))
        ans += sum(loop)*(nloop-1)
        ans += sum(loop[0:tail])
        break
    else:
        ans += aa
        aset.add(aa)
        alist.append(aa)

print(ans)

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

tmp = []

while True:
    tmp.append(x)
    x = pow(x, 2, m)
    if x in tmp:
        break

k = 0
while True:
    if tmp[k] == x:
        break
    k += 1

if k > n:
    print(sum(tmp[:n]))
else:
    t = k
    a = (n - k) // (len(tmp) - k)
    s = (n - k) % (len(tmp) - k)
    print(sum(tmp[:k]) + sum(tmp[k:]) * a + sum(tmp[k: k + s]))

Solution (Python):
n, x, m = map(int, input().split())
ans = 0
prev_set = set()
prev_list = list()
ans_hist = list()
r = x

for i in range(n):
    if i == 0:
        pass
    else:
        r = (r * r) % m
    
    if r == 0:
        break
    
    if r in prev_set:
        index = prev_list.index(r)
        period = i - index
        count = (n - index) // period
        rest = (n - index) % period

        
        
        if index == 0:
            ans += ans * (count - 1)
        else:
            ans += (ans - ans_hist[index - 1]) * (count - 1)

        ans += sum(prev_list[index:index+rest])
        
        break
    else:
        ans += r
        prev_set.add(r)
        prev_list.append(r)
        ans_hist.append(ans)
print(ans)

Solution (Python):


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


 

start=X%M
rset=set()
rireki=list()
rset.add(start)
rireki.append(start)
ss=0
for j in range(1,M+1):
    start=(start**2)%M
    if start in rset:
        ss=rireki.index(start)
        break
    else:
        rireki.append(start)
        rset.add(start)
nn=len(rireki)
rep=(N-ss)//(nn-ss)
nokori=N-ss-rep*(nn-ss)
loop=rireki[ss:]





if 0 in rireki:
    goukei=sum(rireki)
else:
    goukei=rep*sum(loop)+sum(rireki[:ss])+sum(loop[:nokori])
print(goukei)

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

lis = [x]
flag = [-1 for i in range(m)]
flag[x] = 0
left = -1
right = -1
for i in range(n-1):
    x = x**2 % m
    if flag[x] >= 0:
        left = flag[x]
        right = i
        break
    else:
        lis.append(x)
        flag[x] = i+1

ans = 0
if left == -1:
    ans = sum(lis)
else:
    ans += sum(lis[0:left])
    length = right - left + 1
    ans += sum(lis[left:]) * ((n-left)//length)
    ans += sum(lis[left:left+((n-left)%length)])
print(ans)

Solution (Python):
n,x,m=map(int, input().split())
a=x
ans=a
flg=[0]*m
flg[a]=1
l=[a]
lp=-1

for i in range(1,n):
    tmp=(a*a)%m
    a=tmp
    if flg[a]==1:
        lp = l.index(a)
        break
    else:    
        ans+=tmp
        l.append(a)
        flg[a]=1

if lp != -1:
    l2 = l[lp:]
    tmp = sum(l2)
    b=(n-len(l))//len(l2)
    c=n-len(l)-b*len(l2)
    ans=ans+(b*tmp)+sum(l2[:c])

print(ans)

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

ans = 0

ans += sum(A[:iii])
N -= iii
if N > 0:
    
    l = len(A) - iii
    ans += (N // l) * sum(A[iii:])
    N -= N // l * l
if N > 0:
    
    ans += sum(A[iii:iii + N])

print(ans)
exit()

Solution (Python):
n,x,m=map(int, input().split())
a=x
ans=a
flg=[0]*m
flg[a]=1
l=[a]
lp=-1

for i in range(1,m+1):   
    if n <= i:
        break
    tmp=(a*a)%m
    a=tmp
    if flg[a]==1:
        lp = l.index(a)
        break
    else:    
        ans+=tmp
        l.append(a)
        flg[a]=1

if lp != -1:
    l2 = l[lp:]
    tmp = sum(l2)
    b=(n-len(l))//len(l2)
    c=n-len(l)-b*len(l2)
    ans=ans+(b*tmp)+sum(l2[:c])

print(ans)

Solution (Python):
N, X, M = map(int, input().split())
tmp = X
seq = []
ans = 0
for i in range(N):
  if X in seq:
    break
  seq.append(X)
  X = (X ** 2) % M

ans = sum(seq[:min(N, len(seq))])
N -= len(seq)
if N < 1:
    print(ans)
    exit()
i = seq.index(X)
l = len(seq) - i
ans += sum(seq[i:]) * (N//l)
N %= l
ans += sum(seq[i:i+N])
print(ans)

Solution (Python):

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

s = [0, x]
d = {x: 1}
su = x
ans = x
for i in range(2, n+1):
    x = (x * x) % m
    su += x
    if x in d:
        a = su - s[d[x]]
        ans = s[d[x]] - x
        le = i - d[x]
        rep = (n - d[x] + 1) // le
        ans += a * rep
        amari = (n - d[x] + 1) % le
        for j in range(amari):
            ans += x
            x = (x * x) % m
        break
    else:
        s.append(su)
        d[x] = i
        ans = su
print(ans)