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: Time Limit Exceeded

Solution code:
def main():
    N, X, M = map(int, input().split())
    NN = N
    li = []
    while X not in li and N != 0:
        li = li + [X]
        X = X ** 2 % M
        N -= 1
    
    if N == 0:
        print(sum(x for x in li))

    elif N != 0 and X in li:
        l = len(li)
        s = li.index(X)
        T = l - s
        q = (NN - s) // T
        r = (NN - s) % T
        print(sum(li[i] for i in range(s)) + sum(li[i] for i in range(s, len(li))) * q + sum(li[i] for i in range(s, s + r)))


main()

Submission status: Time Limit Exceeded

Solution code:


def main():
    import sys
    st=set()
    N,X,M=list(map(int,sys.stdin.readline().split()))
    L=[]
    a=-1
    for i in range(N):
        a=pow(X,pow(2,i),M)
        if a in st:
            break
        else:
            st.add(a)
            L.append(a)

    n=N
    if a+1:
        idx=L.index(a)
        res=sum(L[:idx])
        n-=idx

        s=sum(L[idx:])
        length=len(L)-idx
        res+=s*(n//length)
        res+=(sum(L[idx:idx+n%length]))
        print(res)
    else:
        print(sum(N))



main()

Submission status: Time Limit Exceeded

Solution code:
N, X, M = [int(x) for x in input().split()]

seen = set()
front = []
cycle = []
for i in range(N):
    x = pow(X, 2 ** i, M)
    if x in seen:
        index = front.index(x)
        front, cycle = front[:index], front[index:]
        break
    front.append(x)
    seen.add(x)


if N <= len(front):
    print(sum(front[:N]))
    exit()

if N <= len(front) + len(cycle):
    print(sum(front) + sum(cycle[: N - len(front)]))
    exit()

q, r = divmod(N - len(front), len(cycle))

if False:
    A = [pow(X, 2 ** i, M) for i in range(N)]
    B = front + cycle * q + cycle[:r]
    print(A, B)
    assert A == B
print(sum(front) + sum(cycle) * q + sum(cycle[:r]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

n,x,m=map(int,input().split())
s=0
for i in range(n):
  if i==0:
    s+=x
  else:
    x=x**2%m
    s+=x
print(s)

Submission status: Time Limit Exceeded

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

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

ans=x
modnum=ans
for i in range(n-1):
  modnum=mod_(modnum**2,m)
  ans+=modnum
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,X,M = map(int, input().split())
list = [X]
A = X
for i in range(N-1):
  A = (A*A) % M
  list.append(A)
print(sum(list))

Submission status: Time Limit Exceeded

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

def Mod(a,b):
  c = a % b
  return c

List = []
for i in range(N):
  if i == 0:
    List.append(X)
  else:
    List.append(Mod(List[i-1]**2, M))
S = sum(List)
print(S)

Submission status: Time Limit Exceeded

Solution code:
N, X, M = map(int, input().split())
NN = N
li = []
while X not in li and N != 0:
    li = li + [X]
    X = X ** 2 % M
    N -= 1
    
if N == 0:
    print(sum(x for x in li))

elif N != 0 and X in li:
    l = len(li)
    s = li.index(X)
    T = l - s
    q = (NN - s) // T
    r = (NN - s) % T
    print(sum(li[i] for i in range(s)) + sum(li[i] for i in range(s, len(li))) * q
              + sum(li[i] for i in range(s, s + r)))

Submission status: Time Limit Exceeded

Solution code:
n=list(map(int,input().split()))
result = n[1]
next_in = n[1]*n[1]
for i in range(n[0]-1):
    if next_in < n[2]:
        result += next_in
        next_in = pow(next_in,2)
        continue
    elif next_in > n[2]:
        c = next_in % n[2]
        result += c
        next_in = pow(c,2)
        continue
    else:
        next_in = pow(next_in,2)
        continue
print(result)

Submission status: Time Limit Exceeded

Solution code:
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
from itertools import permutations
def solve(N,X,M):
    ans=X
    A=X
    for _ in range(N-1):
        A=A**2%M
        if A==0:
            break
        ans+=A
    return ans


N,X,M=readMap()
print(solve(N,X,M))

Submission status: Time Limit Exceeded

Solution code:
indice, nbDepart, diviseur = [int(k) for k in input().split()]

sum = nbDepart
valeur = nbDepart

for k in range(indice-1):
  valeur = valeur**2 % diviseur
  sum += valeur
print(sum)

Submission status: Time Limit Exceeded

Solution code:
n=list(map(int,input().split()))
result = n[1]
next_in = n[1]*n[1]
for i in range(n[0]-1):
    if next_in < n[2]:
        result += next_in
        next_in = next_in*next_in
        continue
    if next_in == n[2]:
        next_in = next_in*next_in
        continue
    if next_in > n[2]:
        c = next_in % n[2]
        result += c
        next_in = c*c
        continue
print(result)

Submission status: Time Limit Exceeded

Solution code:
a = input().split()
n = int(a[0])
x = int(a[1])
m = int(a[2])

y = 0
for i in range(1, n + 1):
  if i == 1:
    y += x
  
  else:
    z = (x % m) ** (2 ** (i - 1)) % m
    y += z
  
  if i > 1 and z == 0:
    break

print(y)

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
prev = x
for i in range(2, n+1):
  if prev:
    prev = pow(prev, 2, m)
    x += prev
  else:
    break
print(x)

Submission status: Time Limit Exceeded

Solution code:
n,x,m=input().split()
n=int(n)
x=int(x)
m=int(m)
a1=x
b=[]
for i in range(n-1):
    an=a1**2%m
    b.append(an)
    a1=an
print(sum(b)+x)

Submission status: Time Limit Exceeded

Solution code:
def main():

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

    ans = X
    tmp = X

    for i in range(N-1):
        tmp = tmp**2 % M
        ans = ans + tmp
        #print(i, tmp)

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
indice, nbDepart, diviseur = [int(k) for k in input().split()]

sum = nbDepart
valeur = nbDepart

for k in range(indice-1):
  valeur = valeur**2 % diviseur
  sum += valeur
print(sum)

Submission status: Time Limit Exceeded

Solution code:
n,x,m=map(int,input().split())
ans=x
a=[x]
if n==1:
  print(ans)
else:
  for i in range(2,n+1):
    tmp=a[-1]**2%m
    if tmp not in a:
      a.append(tmp)
      ans+=tmp
    else:
      t=a.index(tmp)
      if len(a)-t>=n-i+1:
        ans+=sum(a[t:t+n-i+1])
        break
      else:
        t=a.index(tmp)
        tmp_a=(n-i+1)//(len(a)-t)
        tmp_b=(n-i+1)-(len(a)-t)*tmp_a
        ans+=sum(a[t:])*tmp_a+sum(a[t:t+tmp_b])
        break
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m=input().split()
n=int(n)
x=int(x)
m=int(m)
a1=x
s=0
for i in range(n-1):
    an=a1**2%m
    s+=an
    a1=an
print(s+x)

Submission status: Time Limit Exceeded

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

def ans(a):
    x_2 = (a ** 2) % m
    return(x_2)

re = x

for i in range(n - 1):
    #print(x)
    if x % m == 0:
        x = 0
        break
    else:
        x = ans(x)

    re += x
    #print("ans" + str(re))

print(re)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int,input().split())
l = []
l.append(x)
for i in range(n-1):
	new = pow(x,2)
	val = new%m
	if val<=m:
		x = val
		l.append(val)
	else:
		break	
	
	
	
	


print(sum(l))

Submission status: Time Limit Exceeded

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

def ans(a):
    x_2 = (a ** 2) % m
    return(x_2)

re = x

for i in range(n - 1):
    #print(x)
    x = ans(x)

    re += x
    #print("ans" + str(re))

print(re)

Submission status: Time Limit Exceeded

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

data = [X for i in range(M+1)]
val = set([X])

start = -1
period = -1
for i in range(1,M+1):
    data[i] = pow(data[i-1],2,M)
    if data[i] in val:
        for j in range(0,i):
            if data[j]==data[i]:
                start = j
                period = i-j
                break
    else:
        val.add(data[i])

if N<=M:
    print(sum(data[:N]))
else:
    res = sum(data[:start])

    backet = sum(data[start:start+period])
    Q = (N - start) // period
    R = (N- start) % period

    res += backet*Q + sum(data[start:start+R])
    print(res)

Submission status: Time Limit Exceeded

Solution code:
def calc_dynamic(n, x, m):
    # 結果を保持する辞書
    cal_result = {}

    # 初期値の設定
    cal_result[1] = x

    if n == 1:
        return x

    for i in range(1, n):
        cal_result[i+1] = cal_result[i] ** 2 % m

    #return cal_result[n]
    return sum(cal_result.values())

def calc_dynamic2(n, x, m):
    cal_result_0 = 0
    cal_result_1 = 0

    # 初期値の設定
    cal_result_0 = x
    total = x

    if n == 1:
        return x

    for i in range(1, n):
        cal_result_1 = cal_result_0 * cal_result_0 % m
        cal_result_0 = cal_result_1
        total += cal_result_1

    return total

[n, x, m] = map(lambda x: int(x), input().split(" "))
print(calc_dynamic2(n, x, m))

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int,input().split())
ans = x
for a in range(n-1):
    x = (x ** 2) % m
    ans += x
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
sum = 0
a = x
for i in range(n):
  sum = sum + a
  a = a**2 % m
print(sum)

Submission status: Time Limit Exceeded

Solution code:
def pow(x, n, m):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
            K %= m
        x *= x
        x %= m
        n //= 2

    return (K * x) % m

def main():
    import sys
    st=set()
    N,X,M=list(map(int,sys.stdin.readline().split()))
    L=[]
    a=-1
    for i in range(N):
        a=pow(X,2**i,M)
        if a in st:
            break
        else:
            st.add(a)
            L.append(a)

    n=N
    if a+1:
        idx=L.index(a)
        res=sum(L[:idx])
        n-=idx

        s=sum(L[idx:])
        length=len(L)-idx
        res+=s*(n//length)
        res+=(sum(L[idx:idx+n%length]))
        print(res)
    else:
        print(sum(N))



main()

Submission status: Time Limit Exceeded

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

for _ in range(n-1):
    a = a**2 % m
    result += a

print(result)

Submission status: Time Limit Exceeded

Solution code:
#create date: 2020-09-19 21:14

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, x, m = na()
    ans = x
    l = [x]
    a = x
    for i in range(n-1):
        a = a**2
        a %= m
        if a == 0:
            ans += a
            print(ans)
            quit()
        if a in l:
            #print(a, l)
            j = l.index(a)
            r = i - j + 1
            res = sum(l[j:])
            k = ((n-i-1)%r)
            #print(k, n-i-1, r, l[j:(j+k)])
            ans += (n-i-1)//r * res + sum(l[j:(j+k)])
            break
        l.append(a)
        ans += a
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,X,M = map(int,input().split())
A = [0]*M
S = 0
r = X
A[r-1] = 1
d = 0
I = 0
for i in range(1,M):
    r = (r*r) % M
    if A[r-1] == 0:
        A[r-1] = i+1
    else:
        I = A[r-1]
        j = i+1
        d = j-I
        break
r = X
if I == 0:
    I = N
for i in range(I):
    S += r
    r = (r*r) % M
if d != 0:
    t,u = (N-I)//d,(N-I)%d
    s = 0
    for i in range(d):
        s += r
        r = (r*r) % M
    S += s*t
    for i in range(u):
        S += r
        r = (r*r) % M
print(S)

Submission status: Time Limit Exceeded

Solution code:
a,b,c=input().split()
a=int(a)
b=int(b)
c=int(c)
a1=b
an=b
total=0
for i in range(a-1):
    total=total+(an*an)%c
    an=(an*an)%c
total=total+a1
print(total)

Submission status: Time Limit Exceeded

Solution code:
def pow(x, n, m):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
            K %= m
        x *= x
        x %= m
        n //= 2

    return (K * x) % m

def main():
    import sys
    N,X,M=list(map(int,sys.stdin.readline().split()))
    L=[]
    a=-1
    for i in range(N):
        a=pow(X,2**i,M)
        if a in L:
            break
        else:
            L.append(a)

    n=N
    if a+1:
        idx=L.index(a)
        res=sum(L[:idx])
        n-=idx

        s=sum(L[idx:])
        length=len(L)-idx
        res+=s*(n//length)
        res+=(sum(L[idx:idx+n%length]))
        print(res)
    else:
        print(sum(N))



main()

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int,input().split())
a = []
a.append(0)
a.append(x)
for i in range(1,n):
  #tmp = (a[i]**2)%m
  tmp = (a[i]%m)*(a[i]%m)
  tmp = tmp%m
  a.append(tmp)
  if tmp==0:
    break
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
def zen(x, y):
    wk = x % y
    return wk

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

ans = 0
tm = x

for num in range(n):
    ans = ans + zen(tm ,m)
    tm = zen(tm**2 ,m)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = list(map(int,list(input().split())))
l=x
s=x
for i in range(1,n):
  t=l
  l=(t**2)%m
  s+=l
print(s)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = list(map(int, input().split()))
num=x
count=0
for i in range(n):
    count+=num
    num=num*num%m
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, X, M = map(int,input().split())
visited = [(-1,-1)]*M
ans = 0
for i in range(N):
    if visited[X][0] > 0:
        d = ans - visited[X][0]
        left = N-i
        length = i-visited[X][1]
        ans += (left//length)*d
        left %= length
        for j in range(left):
            ans += X
            X = X*X % M
        break
    visited[X] = (ans, i)
    ans += X
    X = X*X % M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m=map(int,input().split())
s=0
for i in range(n):
    s+=x%m
    x=x**2
    if(x%m==0):
        break
print(s)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 19 13:14:17 2020

@author: Admin
"""


n,x,m=input().split()
m=int(m)
a=[int(x)]
s=int(x)
for i in range(1,int(n)):
    zp=a[i-1]
    z=zp**2
    a.append(z%m)
    s+=a[i]
print(s)

Submission status: Time Limit Exceeded

Solution code:
#t=int(input())
#for i in range(t):
n,x,m=map(int,input().split())
a=x
ans=x
for i in range(1,n):
  b=(a*a)%m
  a=b
  if b>0:
    ans+=b
  else:
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
prev = x
for i in range(2, n+1):
  if prev:
    t = pow(prev, 2, m)
    prev = t
    x+= t
  else:
    break
print(x)

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
sum_val = 0
val = x
for i in range(n):
  remain = val%m
  if(remain == 0):
    break
  else:
    sum_val += remain
    val = (val**2)
  #print(val, remain)

print(sum_val)

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
div = [x]
while (div[-1] * div[-1]) // m != div[0]:
  div.append((div[-1] * div[-1]) // m)

x = (n // len(div)) * sum(div)
y = sum(div[:(n % len(div))]) if n % len(div) else 0
print(x + y)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 19 13:14:17 2020

@author: Admin
"""

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

n,x,m=input().split()
a=[int(x)]
for i in range(1,int(n)):
    zp=a[i-1]
    z=zp**2
    a.append(f(z,int(m)))
    
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
N,X,M = map(int,input().split())
R = [X]
m = min(N,M)
for i in range(m):
    r = R[-1]
    r = r**2%M
    if r in R:
        break
    R.append(r)
for i in range(len(R)):
    if r == R[i]:
        break
a = 0
b = sum(R)
for j in range(i):
    a += R[j]
    b -= R[j]
n = len(R) - i
t = N - i
p = t // n
q = t % n
c = 0
for j in range(q):
    c += R[i+j]
ans = a + b*p + c
print(ans)

Submission status: Accepted

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

idx = [-1] * M
A = []
total = 0
length = 0

while idx[X] == -1:
    A.append(X)
    idx[X] = length
    length += 1
    total += X
    X = pow(X, 2, M)

cycle = length - idx[X]
cycle_sum = sum(A[idx[X]:length])

ans = 0
if length >= N:
    print(sum(A[:N]))
else:
    ans += total
    N -= length
    l, m = divmod(N, cycle)
    ans += cycle_sum * l
    ans += sum(A[idx[X]:idx[X] + m])
    print(ans)

Submission status: Accepted

Solution code:
import sys
import re
import queue
import collections
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []


def main():
	N,X,M=i_map()

	Y = X

	went_array = []
	for i in range(0,M):
		went_array.append(-1)

	loop_flag = False
	first = -1
	second = -1
	value = -1
	for i in range(0,N):

		if(went_array[Y] != -1):
			loop_flag = True
			first = went_array[Y]
			second = i
			value = Y
			break

		went_array[Y] = i
		Y = (Y*Y) % M

	if(loop_flag == False):
		Z = X
		sum = 0

		for i in range(0,N):
			sum += Z
			Z = (Z*Z)%M

		print(sum)

	else:
		Z = X
		sum1 = 0
		for i in range(0,first):
			sum1 += Z
			Z = (Z*Z)%M

		Z = value
		cum = []
		cum.append(Z)
		Z = (Z*Z) %M
		for i in range(1,second-first):
			cum.append(cum[i-1]+Z)
			Z = (Z*Z) %M

		sum2 = ((N-first)//(second-first))*cum[second-first-1]

		if((N-first)%(second-first) == 0):
			print(sum1 + sum2)
		else:
			sum3 = cum[((N-first)%(second-first)-1)]
			print(sum1 + sum2 + sum3)


	return

if __name__ == '__main__':
	main()

Submission status: Accepted

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

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

a_list = [x]
a = x
i = 1
while (i<n and i < m+1):
    a = (a*a) % m
    a_list.append(a)
    i += 1
    
#print(i)
#print(a_list)
    
if i == n:
  ans = sum(a_list)
else:
    b = a_list.index(a)
    sum1 = sum(a_list[:b+1])
    sum2 = sum(a_list[b+1:i])
    blen = i-b-1
    repeat = (n-b-1) // blen
    amari = (n-b-1) % blen
    sum3 = 0
    if amari != 0:
    	sum3 = sum(a_list[b+1:b+amari+1])
    ans = sum1 + sum2*repeat + sum3
    #print(blen)
    #print(amari)
    #print(sum1, sum2, repeat, sum3)

print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
X = [-1] * m
P = []
sum_p = 0
while X[x] < 0: # preset
    X[x] = len(P) # pre length
    P.append(sum_p) # pre sum_p
    sum_p += x # now sum_p
    x = x*x % m
cyc_times, nxt_len = divmod(n - X[x], len(P) - X[x])
cyc = (sum_p - P[X[x]]) * cyc_times
remain = P[X[x] + nxt_len]
print(cyc + remain)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
X = [-1] * m
P = []
sum_p = 0
while X[x] == -1: # preset
    X[x] = len(P) # pre length
    P.append(sum_p) # pre sum_p
    sum_p += x # now sum_p
    x = x*x % m
cyc_times, nxt_len = divmod(n - X[x], len(P) - X[x])
cyc = (sum_p - P[X[x]]) * cyc_times
remain = P[X[x] + nxt_len]
print(cyc + remain)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
X = [-1] * m
P = []
sum_p = 0
while X[x] == -1: # preset
    X[x] = len(P) # pre length
    P.append(sum_p) # pre sum_p
    sum_p += x # now sum_p
    x = x*x % m
P.append(sum_p) # full sum_p
p_len = len(P) - 1
cyc_times, nxt_len = divmod(n - X[x], p_len - X[x])
cyc = (sum_p - P[X[x]]) * cyc_times
remain = P[X[x] + nxt_len]
print(cyc + remain)

Submission status: Accepted

Solution code:
N,X,M=map(int,input().split())
table=[X]
visited=[-1]*M
visited[X]=1

ans=X

for i in range(N-1):
    nx=table[i]**2
    nx%=M
    if visited[nx]>0:
        first=table.index(nx)
        oneloop=i+1-first
        rest=N-i-1
        loops=rest//oneloop
        totalofoneloop=sum(table[first:])
        ans+=totalofoneloop*loops
        remain=rest%oneloop
        ans+=sum(table[first:first+remain])
        print(ans)
        exit()
    else:
        table.append(nx)
        visited[nx]=1
        ans+=nx
 

print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
X = [-1] * m
P = []
sum_p = 0
while X[x] == -1: # preset
    X[x] = len(P) # pre length
    P.append(sum_p) # pre sum_p
    sum_p += x # now sum_p
    x = x*x % m
P.append(sum_p) # full sum_p

p_len = len(P) - 1
if n <= p_len:
    print(P[n]) # sum_p
    exit()

cyc_times, nxt_len = divmod(n - X[x], p_len - X[x])
cyc = (sum_p - P[X[x]]) * cyc_times
remain = P[X[x] + nxt_len]
print(cyc + remain)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
P = []
sum_p = 0
X = [-1] * m
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        remain = P[X[x]]
        cyc = (sum_p - remain) * ((n - X[x]) // cyc_len)
        remain += P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # pre_sum
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check & pre_len
for i in range(mn):
    if X[x] > -1:
        cyc_times, nxt_len = divmod(n-X[x], len(P) - X[x])
        cyc = (sum_p - P[X[x]]) * cyc_times
        remain = P[X[x] + nxt_len]
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Submission status: Accepted

Solution code:
# 繰り返しの始まり + 繰り返し + 途中で終わった繰り返し分
N,X,M = map(int,input().split())
p = [0] * (M+2)
sum = [0] * (M+2)
p[X] = 1
sum[1] = X

repeat_start = 0
repeat_end = 0

for i in range(2,N+1):
  X = (X**2) % M
  if p[X] != 0:
    repeat_start = p[X]
    repeat_end = i
    break
  else:
    sum[i] = sum[i-1] + X
    p[X] += i

if repeat_start == 0:
  print(sum[N])
else:
  repeat_cnt,mod=divmod(N-repeat_start+1,repeat_end-repeat_start)
  print(repeat_cnt*(sum[repeat_end-1]-sum[repeat_start-1]) + sum[repeat_start+mod-1])

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # pre_sum
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check & pre_len
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        n -= X[x]
        cyc = (sum_p - P[X[x]]) * (n // cyc_len)
        remain = P[X[x] + n % cyc_len]
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Submission status: Accepted

Solution code:
class findroop:
    def __init__(self, n, nex):
        self.n = n
        self.next = nex

    #遷移start回でループに入る、end回でループする
    #A->B->C->D->B: return=(1, 4)
    #C->D->B->C   : return=(0, 3)
    #O(n)
    def findroop(self, start):
        roopstart = -1
        roopend = -1
        visited = [False for i in range(self.n)]
        visitlist = []
        now = start
        for i in range(self.n):
            if visited[now]:
                roopend = i
                break
            else:
                visited[now] = True
                visitlist.append(now)
                now = self.next(now)
        
        for i in range(len(visitlist)):
            if visitlist[i] == now:
                roopstart = i

        return (roopstart, roopend)


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

fr = findroop(M, lambda x: x**2 % M)

roopstart, roopend = fr.findroop(X)

ans = 0
if N <= roopstart:
    for i in range(N):
        ans += X
        X = (X**2)%M
else:
    for i in range(roopstart):
        ans += X
        X = (X**2)%M

    N -= roopstart
    roopsum = 0
    for i in range(roopend-roopstart):
        roopsum += X
        X = (X**2) % M
    ans += (N // (roopend-roopstart)) * roopsum

    N = N % (roopend-roopstart)

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

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, X, M = LI()
    A = [X]
    seen = set()
    seen.add(X)
    while True:
        an = A[-1]
        an1 = ((an % M) * (an % M)) % M
        if an1 in seen:
            break
        else:
            A.append(an1)
            seen.add(an1)
    start_loop_i = 0
    for i, a in enumerate(A):
        if an1 == a:
            start_loop_i = i
            break
    loop_len = len(A) - start_loop_i
    loop_sum = sum(A[start_loop_i:])

    end = False
    ans = 0
    for i in range(start_loop_i):
        N -= 1
        ans += A[i]
        if N == 0:
            end = True
            break
    if end:
        print(ans)
        return

    ans += loop_sum * (N // loop_len)
    
    if N % loop_len > 0:
        N %= loop_len
        for i in range(N):
            ans += A[start_loop_i + i]
    print(ans)






main()

Submission status: Accepted

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

"""
id[X] Xを何番目に訪問したか。-1で無ければ訪問済み。
Xをメモ  A[i+1] = (A[i] * A[i]) % M
length = ループが終わるまでの長さ
"""

id = [-1] * M
A = []  # 訪問したものをメモ
length = 0
total = 0
while id[X] == -1:
    A.append(X)
    id[X] = length
    length += 1
    total += X
    X = (X * X) % M
syuki = length - id[X]
syukisum = sum(A[id[X] : length])
# for i in range(id[X], length):
#     syukisum += A[i]

ans = 0
if N <= length:
    ans = sum(A[:N])
else:
    ans += total
    N -= length
    loop, res = divmod(N, syuki)
    ans += syukisum * loop
    ans += sum(A[id[X] : id[X] + res])
print(ans)

Submission status: Accepted

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 (sum(ary[:-1]))
  exit()
cyc = ary[chk[x]:]
l1 = len(cyc)
ss = ary[:chk[x]]
l2 = len(ss)
tot = sum(ss) + sum(cyc)*((n-l2)//l1) + sum(cyc[:((n-l2)%l1)])
print (tot)

Submission status: Accepted

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

f=1
w=[]
d=[0]*(m+2)
t=[0]
chk=n
p=x
for i in range(m+1):
    if i!=0: p=p*p%m
    if d[p]: break
    d[p]=1
    w.append(p)
    t.append(t[-1]+p)
    #f*=2
    chk-=1
    if chk==0:
        print(t[-1])
        exit()
ans=0
a=w.index(p)
ans+=t[a]
n-=a
loo=len(w)-a
if n%loo==0:
    ans+=(t[-1]-t[a])*(n//loo)
else:
    ans+=(t[-1]-t[a])*(n//loo)
    ans+=t[a+n%loo]-t[a]
print(ans)

Submission status: Accepted

Solution code:
N,X,M = map(int,input().split())
L = [X]
S = set([X])
idx = N
MOD = 10**9+7
for i in range(1,N):
  X = (X**2%M)
  if len(S) != len(L):
    idx = L.index(X)
    break
  L.append(X)
  S.add(X)

if idx == N:
  print(sum(L[:idx]))
else:
  k = (N-idx)%len(L[idx:])
  print(sum(L[:idx])+((N-idx)//len(L[idx:]))*sum(L[idx:])+sum(L[idx:idx+k]))

Submission status: Accepted

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

A,color=[x],["white" for _ in range(m)]
color[x]="black"
while 1:
    num=A[-1]**2%m
    if color[num]=="black":
        A.append(num)
        break
    else:
        color[num]="black"
        A.append(num)

fixed,loop=[],[]
point=A[-1]
flag=0
for i in A[:-1]:
    if i==point:flag=1

    if flag:loop.append(i)
    else:fixed.append(i)

ans=0
if n<=len(fixed):print(sum(fixed[:n]))
else:
    ans +=sum(fixed)
    div,mod=divmod(n-len(fixed),len(loop))
    ans +=div*sum(loop)
    ans +=sum(loop[:mod])
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, X, M = list(map(int, _in[0].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = 0
    A = X
    head_list = []
    head = set()
    repeat = set()
    for i in range(N):
        if A in head:
            ind = head_list.index(A)
            repeat = head_list[ind:]
            head = head_list[:ind]
            break
        else:
            head.add(A)
            head_list.append(A)
            A = pow(A, 2, M)

    if len(repeat) == 0:
        ans = sum(head)
    else:
        repeat_time = (N - len(head)) // len(repeat)
        tail_len = N - len(head) - repeat_time * len(repeat)
        ans = sum(head) + sum(repeat) * repeat_time + sum(repeat[:tail_len])
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,X,M = map(int,input().split())
i = X%M
L = [i]
S = set([i])
i = i**2 % M
while not i in S:
    L.append(i)
    S.add(i)
    i = i**2 % M
index = L.index(i)
k = (N-index)//len(L[index:])
l = (N-index)%len(L[index:])

# これでうまくいくのたまたまだよ。本当はN<indexの場合分けがひつよう。なんで場合分けするよ
if N<index:
    ans = sum(L[:N])
else:
    ans = sum(L[:index]) + (k*sum(L[index:])) + sum(L[index:index+l])
print(ans)