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: Accepted

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

candicate = [pow(i, 2, M) for i in range(M)]
ans = 0
now = X
A = [0]
X2 = pow(X, 2, M)

d = dict()

flag = True
for i in range(1, N+1):
    if i == 1:
        A.append(X)
    
    else:
        nxt = candicate[A[i-1]]

        if d.get(nxt) == None:
            if nxt == 0:
                A.append(nxt)
                break
            else:
                A.append(nxt)
                d[nxt] = i

        else:
            flag = False
            break


if flag:
    print(sum(A))
else:
    l = d[nxt]
    r = i - 1
    circle_total = 0
    for j in range(l, r+1):
        circle_total += A[j]
    
    for j in range(1, l):
        ans += A[j]

    width = r - l + 1
    N -= (l - 1)
    ans += circle_total * (N // width)

    for j in range(l, l + N % width):
        ans += A[j]

    print(ans)

Submission status: Accepted

Solution code:
import sys

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

if m==1:
    print(0)
    sys.exit()

check=[-1 for i in range(m)]#which tells position

A=[x%m]
check[x%m]=0

roopstart=10**15
for i in range(1,m):
    Ai=(A[i-1]*A[i-1])%m
    if check[Ai]!=-1:
        roopstart=check[Ai]
        break
    else:
        check[Ai]=i
        A.append(Ai)

if roopstart>=n:
    print(sum(A[:n]))
    sys.exit()

s=sum(A[:roopstart])

nn=n-roopstart
rooplen=len(A)-roopstart
roopnum=nn//rooplen
d=nn%rooplen

roopsum=sum(A[roopstart:])

s+=roopsum*roopnum
s+=sum(A[roopstart:roopstart+d])

print(s)

Submission status: Accepted

Solution code:
def solve(n, x, m):
    result = [x]
    checked = [0] * m
    checked[x] = 1
    while len(result) < n:
        x = x * x % m
        if checked[x] > 0:
            break
        result.append(x)
        checked[x] = len(result)
    else:
        return sum(result)

    l = len(result)
    i = checked[x]
    before_len = i - 1
    loop_len = l - i + 1
    loop_sum = sum(result[before_len:])
    d, e = divmod(n - before_len, loop_len)
    ans = sum(result[:before_len]) + loop_sum * d + sum(result[before_len:before_len + e])
    return ans


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

print(solve(n, x, m))

Submission status: Accepted

Solution code:

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

dic = {}
a = x
s = 0
c = m
for i in range(1, n + 1):
    if a not in dic:
        s += a
        dic[a] = [i]
    elif len(dic[a]) == 1:
        s += a * (1 + (n - i) // (i - dic[a][0]))
        dic[a].append(i)
    else:
        break
    a = pow(a, 2, m)
print(s)

Submission status: Accepted

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

if X == 0:
    print(0)
elif X == 1:
    print(N)
else:
    ans = 0
    check, dset = {}, set()

    roop = [0, 0]
    for i in range(2, M):
        j, temp, t = i**2, i, 1
        while j < M:
            temp += j
            t += 1
            j **= 2
        jump = j % M
        roop.append([temp, t, jump])

    while roop[X][1] <= N:
        check[X] = [ans, N]
        dset.add(X)
        ans += roop[X][0]
        N -= roop[X][1]
        X = roop[X][2]
        if X <= 1:
            print(ans + N*X)
            exit()
        if X in dset:
            cyc_ans = ans - check[X][0]
            cyc_N = check[X][1] - N
            ans += cyc_ans * (N//cyc_N)
            N %= cyc_N
    for i in range(N):
        ans += X
        X **= 2
    print(ans)

Submission status: Accepted

Solution code:
n, x, mod = [int(i) for i in input().split()]
ans = x
tmp = x
s = set()
s.add(x)
for i in range(1, n):
    tmp = (tmp * tmp) % mod
    if tmp in s:
        cycle = [tmp]
        t = (tmp * tmp) % mod
        while t != tmp:
            cycle.append(t)
            t = (t * t) % mod
        ans += sum(cycle) * ((n - i) // len(cycle))
        ans += sum(cycle[:(n-i)%len(cycle)])
        break
    else:
        s.add(tmp)
        ans += tmp
print(ans)

Submission status: Accepted

Solution code:
def main():
    n,x,m = map(int,input().split())
    
    #Compute i^2%m
    rem = [(i**2)%m for i in range(m)]

    #Find the cycle and its sum in n
    visited = [False for i in range(m)]
    idx = x
    s = x
    d = 1

    while not visited[idx]:
        visited[idx] = True
        s += rem[idx]
        idx = rem[idx]
        d += 1
        #print(s,idx,d)

    newsum = x
    newidx = x
    newd = 1
    while newidx!=idx:
        newsum += rem[newidx]
        newd += 1
        newidx = rem[newidx]

    #Adds newsum until it gets to idx, until n=newd
    #Cycles with sum s-newsum taking d moves
    d = d - newd
    s = s - newsum

    ans = x
    ansn = 1
    if newd<n:
        ans = newsum
        ansn = newd
    if ansn+d<=n:
        ans += s*((n-ansn)//d)
        ansn += ((n-ansn)//d) * d    
    #print(ans)
    while ansn<n:
        ansn += 1
        ans += rem[idx]
        idx = rem[idx]

    print(ans)
    #print(rem,newsum,newd,s,d)


if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
p=[x]
A=set([x])
f=0
for i in range(n-1):
	p.append(p[-1]**2%m)
	if p[-1] in A:
		f=1
		break
	else:
		A.add(p[-1])
if f==0:
	print(sum(p))
else:
	for i in range(len(p)):
		if p[i]==p[-1]:
			loop=len(p)-i-1
			break
	SUM=sum(p[i:-1])
	ans=sum(p)-p[-1]
	n-=len(p)-1
	ans+=SUM*(n//loop)+sum(p[i:i+n%loop])
	print(ans)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

def inverse(N, mod):
	return (pow(N, mod - 2, mod))

def main():
	N, X, M = getlist()
	if N <= 10 ** 6:
		cnt = 0
		A = X
		cnt += A
		for i in range(N - 1):
			A = (A ** 2) % M
			cnt += A

		print(cnt)
		return

	A = X
	D = defaultdict(int)
	L = [0] * (2 * 10 ** 5)
	L[1] = A
	D[A] = 1

	for i in range(2, N + 2):
		A = (A ** 2) % M
		if D[A] != 0:
			start = D[A]
			loop = i - D[A]
			break
		D[A] = i
		L[i] = A

	ans = 0
	for i in range(start, start + loop):
		ans += L[i]

	p = int((N - start + 1) // loop)
	ans *= p

	for i in range(1, start):
		ans += L[i]

	q = N - loop * p - start + 1
	for i in range(start, start + q):
		ans += L[i]

	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

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

a = X
count = 1
ai = [a]
mapping = [0 for i in range(10**5+1)]
mapping[a] = count
count += 1
for i in range(1, 10**5+1):
    a = (a ** 2 ) % M
    if mapping[a] == 0:
        ai.append(a)
        mapping[a] = count
    else:
        break
    count += 1
s = mapping[a]
e = mapping[ai[-1]]
loop = e - s + 1
# print(s, e, ai)
if N <= e:
    print(sum(ai[:N]))
else:
    syo = (N - e) // loop
    amari = (N - e) % loop
    loop_total = sum(ai[s-1:e])
    # print(loop_total * syo, sum(ai[s-1:s+amari-1]))
    ans = sum(ai) + loop_total * syo + sum(ai[s-1:s+amari-1])
    print(ans)
# print(s, e, syo, amari, loop_total)

Submission status: Accepted

Solution code:
n, x, m = map(int,input().split())
rem = [0] * m
chk = [0] * (m + 1)
rem[0] = x
if x == 0:
  print(0)
  exit()

for i in range(1,m):
  rem[i] = (rem[i - 1] ** 2) % m
  if chk[rem[i - 1] ** 2 % m] > 1:
    temp1 = (rem[i - 1] ** 2) % m
    temp2 = i
  else:
    temp1 = (rem[i - 1] ** 2) % m
    temp2 = i

for i in range(m):
  if rem[i] == temp1:
    temp3 = i
    break

if temp2 != temp3:
  num = (n - temp3) // (temp2 - temp3)
  S = sum(rem[:temp3]) + sum(rem[temp3:temp2]) * num + sum(rem[temp3:n - (num * (temp2 - temp3))])
  print(S)
else:
  print(sum(rem))

Submission status: Accepted

Solution code:
n,x,m=map(int, input().split())
alist=[]
blist=[0]*m
num=x%m
while blist[num]==0:
  alist.append(num)
  blist[num]=1
  num=(num**2)%m
num1=alist.index(num)
num2=len(alist)
if x==1:
  print(n)
elif n<=num1:
  print(sum(alist[0:n]))
else:
  cycle=(n-num1)//(num2-num1)
  print(sum(alist[0:num1])+cycle*sum(alist[num1:num2+1])+sum(alist[num1:n-cycle*(num2-num1)]))

Submission status: Accepted

Solution code:
def pow_mod(x, y, mod=10**9 + 7):
    if y == 0:
        return 1
    res = 1
    for i in range(y.bit_length()):
        if y & (1 << i):
            res *= x
            res %= mod
        x *= x
        x %= mod
    return res


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

order = [0] * (m+1)
cnt = [-1] * (m+1)

now = x
a = -1
b = -1
for i in range(n):
    if cnt[now] != -1:
        a = cnt[now]
        b = i
        break
    order[i] = now
    cnt[now] = i
    now = pow_mod(now, 2, m)

if a == -1 and b == -1:
    print(sum(order))
    exit()

ans = 0
roop = [0]
for i in range(b):
    if i < a:
        ans += order[i]
    else:
        roop.append(order[i] + roop[-1])

n -= a

tmp = n % (b-a)
freq = n // (b-a)

ans += roop[-1] * freq
ans += roop[tmp]
print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
D = {i:0 for i in range(M)}
L = [X]
c = X
D[X]=0
S = X
for i in range(1, N):
  c = (c**2)%M
  if D[c]==0:
    D[c] = i
    L.append(c)
    S += c
    continue
  else:
    p, q = D[c], i
    break
else:
  print(S)
  exit()  
cycle = L[p:q]
cycle_sum = sum(cycle)
cycle_num = (N-q)//(q-p)
rest = (N-q)%(q-p)
S += cycle_sum*cycle_num
S += sum(cycle[:rest])
print(S)

Submission status: Accepted

Solution code:
N,X,M=map(int,input().split())
dist=[0 for i in range(M)]
A=X
loopin=-1
loopout=-1
ans=[0]
for i in range(N+1):
    if dist[A]!=0:
        loopin=dist[A]
        loopout=i
        ans.append(ans[-1]+A)
        break
    else:
        dist[A]=i
        ans.append(ans[-1]+A)
        A=(A*A)%M
if loopin==-1:
    print(ans[N])
    exit()
#print(roopin,roopout)
#print(ans)
A=X
loop=loopout-loopin
def solve(l,r):
    assert 0<=l and l<=r
    if r<=loopout:
        return ans[r]-ans[l]
    if l<loopin:
        return ans[loopin]-ans[l]+solve(loopin,r)
    x=(l-loopin)//loop
    y=(r-loopin)//loop
    #x*loop+loopin<=l<(x+1)*loop+loopin
    #y*loop+loopin<=r<(y+1)*loop+loopin
    if x==y:
        return ans[r-y*loop]-ans[l-x*loop]
    #以降はx<y
    tmp1=ans[l-x*loop]-ans[loopin]
    tmp2=(ans[loopout]-ans[loopin])*(y-x)
    tmp3=ans[r-y*loop]-ans[loopin]
    #print(l,r,x,y,tmp1,tmp2,tmp3)
    return tmp1+tmp2+tmp3
print(solve(0,N))

Submission status: Accepted

Solution code:
N,X,M=map(int,input().split())
lst=[]
n,s=X,0
for i in range(N):
  if n in lst:break
  lst.append(n)
  n=(n*n)%M
if len(lst)<N:
  k=lst.index(n)
  s1=sum(lst[:k])
  s2=sum(lst[k:])*((N-k)//(len(lst)-k))
  s3=sum(lst[k:k+(N-k)%(len(lst)-k)])
  s=s1+s2+s3
else:s=sum(lst)
print(s)

Submission status: Accepted

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

loop = [0]*m

a = x
is_loop = False
for i in range(n):
        if loop[a] == 1:
            # あまりがループしている
            loop[a] += 1
            is_loop = True
            break
        else:
            # ループしていない
            loop[a] = 1
            a = (a**2)%m

if not is_loop:
    # ループしなかった
    ans = 0
    for i in range(m):
        ans += i*loop[i]
    print(ans)
else:
    # ループした
    # 1. ループ長を求める
    def get_loop_length(b):
        c = 1
        s = b
        b_tmp = b
        while True:
            b_tmp = (b_tmp**2)%m
            if b == b_tmp:
                return c, s
            else:
                c += 1
                s += b_tmp
    loop_length, loop_sum = get_loop_length(a)
    # 2. ループに入るまでをシミュレーション、計算、シミュレーション
    ans = 0
    b = x
    # ループまで
    while b != a:
        ans += b
        b = (b**2)%m
        n -= 1
    # ループ中
    ans += loop_sum*(n//loop_length)
    n = n % loop_length
    b = a
    for i in range(n):
        ans += b
        b = (b**2)%m
    print(ans)

Submission status: Accepted

Solution code:
def solve(N, X, M):
    seen = set()
    front = [X]
    cycle = []
    for i in range(N - 1):
        x = (front[-1] * front[-1]) % M
        if x in seen:  # seen can't be more than M since x is < M
            index = front.index(x)
            front, cycle = front[:index], front[index:]
            break
        front.append(x)
        seen.add(x)
    if N <= len(front):
        return sum(front[:N])

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

    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
    return sum(front) + sum(cycle) * q + sum(cycle[:r])


N, X, M = [int(x) for x in input().split()]
print(solve(N, X, M))

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
cnt2=set()
cnt2.add(x)
cnt3=[x]
cnt4=0
cnt5=0
cnt6=x
for i in range(1,m+10):
    num2=pow(cnt6,2,m)
    if num2 in cnt2:
        for j in range(len(cnt3)):
            if cnt3[j]==num2:
                cnt7=j
                break
        cnt10=len(cnt3)-cnt7
        num4=sum(cnt3[:cnt7])
        cnt4=len(cnt3)
        break
    cnt2.add(num2)
    cnt3.append(num2)
    cnt6=num2
    if num2==0:
        ans=sum(cnt3)
        cnt5=1
        break
if cnt5==0 and n>cnt4:
    ans=num4
    n-=cnt7
    ans+=(n//cnt10)*sum(cnt3[cnt7:])
    ans+=sum(cnt3[cnt7:(n%cnt10)+cnt7])
if cnt4>=n:
    ans=sum(cnt3[:n])
print(ans)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n,x,m = inm()
k = -1
a = x
h = {}
f = [-1]*100001
f[0] = a
h[a] = 0
for i in range(1,n):
    a = (a*a)%m
    f[i] = a
    if a in h:
        k = i
        j = h[a]
        break
    else:
        h[a] = i
#ddprint(f"{f[:15]}")
if k<0:
    print(sum(f[:n]))
else:
    p = k-j
    q = (n-j)//p
    r = (n-j)%p
    #ddprint(f" /{k=} {j=} {f[j]} {f[k]} {p=} {q=} {r=}")
    print(sum(f[:j+r])+q*sum(f[j:k]))

Submission status: Accepted

Solution code:
n,x,m = map(int,input().split())
rec = [-1 for _ in range(m)]
rec[x] += 1
now = x
cnt = 1
while True:
  now = now ** 2
  now %= m
  #print(now)
  if rec[now] == -1:
    rec[now] = cnt
    cnt += 1
    #print(now,cnt)
  else:
    #print(cnt)
    #print(rec[now])
    break
end = rec[now]
cyc = cnt - end
#print(rec)
#print(end,cyc)
if n <= end:
  ans = 0
  now = x
  for _ in range(n):
    ans += now
    now **= 2
    now %= m
  print(ans)
  exit()
ans = 0
now = x
for i in range(end):
  ans += now
  now **= 2
  now %= m
  n -= 1
ans2 = 0
#print(n,ans)
for i in range(cyc):
  ans2 += now
  #print(now)
  now **= 2
  now %= m
#print(ans2)
db = n // cyc
n %= cyc
ans += ans2 * db
#print(ans,n,now)
ans3 = 0
for _ in range(n):
  ans3 += now
  now **= 2
  now %= m
  #print(now)
#print(ans3)
print(ans+ans3)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
di = {}
for i in range(m+1):
    di[i] = -1
li = []
for i in range(m+1):
    li.append(x)
    di[x] = i
    x = pow(x, 2, m)
    if di[x]  >= 0:
        break
#print(li)
#print(x)
ans = 0
#print(di[x])
for j in range(di[x]):
    ans += li[j]
loop_sum = 0
for j in range(di[x], i+1):
    loop_sum += li[j]
#print(loop_sum)
loop = i+1-di[x] #1ループ何個か
#print(loop)
n -= di[x]
k = n//loop # 何回ループするか
ans += loop_sum * k
#print(ans)
kk = n-k*loop #残り
#print(kk)
ans += sum(li[di[x]:di[x]+kk])
print(ans)

Submission status: Accepted

Solution code:
n,x,m = map(int, raw_input().split())
ans = 0

seen = {}
reverse = {}
c = 0
while(x not in seen):
	seen[x] = c
	reverse[c] = x
	c+=1
	x = (x**2) % m
#print seen[x], c-1 
#print [(key, reverse[key])for key in sorted(reverse.keys())]
def f(n,a,b,reverse):
	ans = 0
	#print a,b
	for i in xrange(b+1):
		if n > 0:
			ans += reverse[i]
			n-=1
		else:
			break
	if n > 0:
		t = sum([reverse[uu] for uu in xrange(a,b+1)] or [0])
		ans += n/(b-a+1) * t
		n %= (b-a+1)

		for i in xrange(a,b+1):
			if n > 0:
				ans += reverse[i]
				n-=1
			else:
				break

	return ans


print f(n, seen[x], c-1, reverse)

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
if n<=m+1:
    s=0
    a=x
    for c in range(n):
        s+=a
        a=pow(a,2,m)
else:
    l=[0]*m
    a=x
    l[a]=1
    for c in range(2,m+2):
        a=pow(a,2,m)
        if l[a]>0:
            d1=l[a]
            d2=c
            d3=a
            break
        l[a]=c
    q=(n-d1)//(d2-d1)
    r=(n-d1)%(d2-d1)+d1
    s=0
    for c in range(d2-d1):
        s+=a
        a=pow(a,2,m)
    s*=q
    for c in range(r):
        s+=x
        x=pow(x,2,m)
print(s)

Submission status: Accepted

Solution code:
#from math import *
import fractions
import sys
import collections
import itertools
import pprint
from collections import deque
from heapq import *
import copy
N,X,M=map(int,input().split())
l=[0]*(M+1)
l[X]=1
X2=X
ans=0
for i in range(10**5+1):
    #print(X)
    X=pow(X,2,M)
    if l[X]==0:
        l[X]=i+2
    else:
        start=l[X]
        end=i+2
        #print(i+1,l[X])
        break
#print(l)
res=[]
X=X2
loop=[]
#print(start,end)
for i in range(start-1):
    res.append(X)
    X=pow(X,2,M)
for i in range(start,end):
    loop.append(X)
    X=pow(X,2,M)
#print(res,loop)
loopsum=sum(loop)
if N<=len(res):
    for i in range(N):
        ans=ans+res[i]
else:
    for i in range(len(res)):
        ans=ans+res[i]
    loopnum=(N-len(res))//len(loop)
    loopres=(N-len(res))%len(loop)
    for i in range(loopres):
        ans=ans+loop[i]
    ans=ans+loopnum*loopsum
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,x,m = list(map(int, input().split()))
v = x
seen = [0]*m
c = 0
val = 0
count = 0
tmp = 0
if n>m:
    while True:
        if seen[v]==2:
            break
        if seen[v]==1:
            count += 1
            tmp += v
        else:
            val += v
            c += 1
        seen[v] += 1
        v = (v**2)%m
    ans = val + ((n-c)//count) * tmp
    for i in range((n-c)%(count)):
        ans += v
        v = (v**2)%m
else:
    ans = 0
    v = x
    for i in range(n):
        ans += v
        v = (v**2)%m
print(ans)

Submission status: Accepted

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

i = 0
a = x
aa = set()
aal = []
s = 0
while a not in aa:
    aa.add(a)
    aal.append(a)
    s += a
    i += 1
    if i == n:
        print(s)
        exit(0)
    a = (a ** 2) % m
    if a == 0:
        print(s)
        exit(0)
st  = aal.index(a)
cont = aal[st:]
nc = len(cont)
n -= st
ans = sum(aal[:st]) + sum(cont) * (n // nc) + sum(cont[:(n % nc)])
print(ans)

Submission status: Accepted

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

    n = [-1] * M
    n[X] = 0

    A = X
    history = [X]
    loop_start = -1
    loop_start_num = -1
    for i in range(1, M+2):
        Anext = A*A % M
        if n[Anext] != -1:
            loop_start = n[Anext]
            loop_start_num = Anext
            break
        history.append(Anext)
        n[Anext] = i
        A = Anext

    # print(n, loop_start,loop_start_num, history)
    ans = 0
    for i in range(min(loop_start, N)):
        ans += history[i]
        N -= 1
    
    loop = history[loop_start:]
    loop_len = len(loop)
    sum_loop = sum(loop)
    # print(sum_loop)

    n_loop = N // loop_len
    ans += sum_loop * n_loop
    N -= loop_len * n_loop

    for i in range(N):
        ans += loop[i]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a = [int(s) for s in input().split()]
b = a[1]
c = [b]
d = {b:0}
flag = int(0)
k = int(0)
t = int(0)
m = int(0)
suma = int(0)
sumb = int(0)
cnt = int(0)
newc = []
newnewc = []

for i in range(1, a[0]):
    b = (b ** 2) % a[2]
    if d.get(b) == None:
        d[b] = i
        c.append(b)
    else:
        flag = 1
        sumb = sum(c)
        k = int(c.index(b))
        newc = c[k:]
        suma = sum(newc)
        k = len(newc)
        t = i
        m = (a[0] - t) % k
        break

if flag == 1:
    newnewc = newc[:m]
    print((a[0] - t) // k * suma + sumb + sum(newnewc))
else:
    print(sum(c))

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
from fractions import Fraction
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
INF = float("inf")

N,X,M = map(int,input().split())
A = [0]*100010
A[0] = X
d = defaultdict(int)
d[X] = 1
l = [X]

ans = X
for i in range(1,N):
    num = pow(A[i-1],2,M)
    l.append(num)
    if d[num] == 0:
        A[i] = num
        d[num] += 1
        ans += num
    else:
        kaburi = num
        break
else:
    print(ans)
    exit()

kaburi_index = l.index(kaburi)
loop_len = len(l)-1-kaburi_index
loop_sum = sum(l[kaburi_index:len(l)-1])

nokori = N-i
loop = nokori//loop_len
amari = nokori%loop_len

ans += loop_sum*loop
ans += sum(l[kaburi_index:kaburi_index+amari])
#print(A)

print(ans)

Submission status: Accepted

Solution code:
N,X,M = map(int,input().split(" "))
q = [-1] * (M + 1)
A = X
i = 0
su = []
p1 = 0
p2 = 0
while q[A] == -1:
    q[A] = i
    su.append(A)
    A = (A * A) % M
    i += 1

if N == len(su):
    print(sum(su))
else:
    r = q[A]
    r2 = (N - r) % (i - r)

    ans1 = sum(su[0:r])
    ans2 = sum(su[r:r + r2])
    ans3 = sum(su[r::])

    print(ans1 + ans2 + ans3 * ((N - r) // (i - r)))

Submission status: Accepted

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

ai = x
i = 0

memo = []
d = {}
tmp = 0

while True:
    if ai in d:
        break
    d[ai] = i
    memo.append(ai)

    ai = (ai ** 2) % m
    i += 1

s = d[ai]
e = i
su = sum(memo[s:])

if n <= e+1:
    print(sum(memo[0:n]))
else:
    zan = n - s
    ans = sum(memo[:s]) + (zan // (e-s)) * su
    if zan % (e-s):
        ans += sum(memo[s:s+(zan % (e-s))])
    print(ans)

Submission status: Accepted

Solution code:
N,X,M=map(int,input().split())
A=[0 for i in range(10**5)]
A[X]=1
c=[]
d=[]
now=X
for i in range(2,N+1):
  now=now**2%M
  if A[now]==0:
    A[now]=i
  else:
    s=A[now]
    p=i-s
    cycle=[0 for i in range(p)]
    f=[]
    for j in range(10**5):
      if s<=A[j]<i:
        cycle[A[j]-s]=j
      if A[j]<s and A[j]!=0:
        f.append(j)
    c=cycle
    d=f
    break
if c==[]:
  ans=0
  for i in range(len(A)):
    if A[i]!=0:
      ans+=i
  print(ans)
else:
  x=len(d)
  y=len(c)
  ccount=(N-x)//y
  amari=(N-x)%y
  ans=sum(d)+sum(c)*ccount+sum(c[:amari])
  print(ans)

Submission status: Accepted

Solution code:
import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, X, M = map(int, input().split())
    L = [X]
    D = [0] * M
    D[X] = 1
    k = 2
    while k < N + 1:

        # k回目
        l = L[-1] ** 2 % M


        if D[l] != 0:
            n = N - k+1  # 残り回数
            one_cycle = k - D[l]
            mass = sum(L[D[l]-1:])
            ans = n//one_cycle *mass
            res = sum(L[D[l]-1:D[l]+(n%one_cycle)-1])
            print(ans +res +sum(L))
            exit()

        if l == 0:
            print(sum(L))
            exit()

        L.append(l)
        D[l] =k
        k += 1

    print(sum(L))


if __name__ == "__main__":
    main()

# \n

Submission status: Accepted

Solution code:
N,X,M = map(int,input().split())
c1 = [X]
c2 = {X}
ans = X
for i in range(N-1):
    X = pow(X,2,M)
#    print(X)
    if X not in c2:
        c1.append(X)
        c2.add(X)
        ans += X
    else:
        b = c1.index(X)
        break
else:
    print(ans)
    exit()
l = len(c1) - b
t = N-i -1
ans += (t//l) * sum(c1[b:]) + sum(c1[b:b+t%l])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n, x, m = map(int, input().split())
    sedic = dict()
    sedic[x] = 1
    wa=[x]
    for i in range(2, min(10**5+100,n+1)):
        x = (x**2) % m
        if x in sedic:
            ans=sum(wa)
            roop,amari=divmod(n-i,i-sedic[x])
            ans+=sum(wa[sedic[x]-1:])*roop
            ans+=sum(wa[sedic[x]-1:sedic[x]+amari])
            print(ans)
            break
        sedic[x]=i
        wa.append(x)
    else:
        print(sum(wa))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

col=[x]
sude=[0]*m
sude[x]=1
now=x
ishu=0
hajimari=0
for i in range(m):
    now**=2
    now%=m
    #print(now)
    if(sude[now]==0):
        sude[now]=i+2
        col.append(now)
    else:
        ishu=i-sude[now]+2
        hajimari=sude[now]-1
        break


#print(ishu,hajimari,col)

saisho=0
loop=0
for i in range(hajimari):
    saisho+=col[i]
for i in range(hajimari,len(col)):
    loop+=col[i]

#print(saisho,loop)

ans=0

if(n<hajimari):
    ans+=col[i]
else:
    ans=saisho+loop*((n-hajimari)//ishu)
    nokori=n-hajimari-ishu*((n-hajimari)//ishu)
    for i in range(hajimari,hajimari+nokori):
        ans+=col[i]

print(ans)

Submission status: Accepted

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

order = []
hist = [0] * M

for i in range(N):
    if hist[X]:
        j = order.index(X)
        rem = N-i
        d,m = divmod(rem,i-j)
        for k in order[j:]:
            hist[k] += d
        for k in order[j:j+m]:
            hist[k] += 1
        break
    order.append(X)
    hist[X] += 1
    X = (X*X)%M

ans = 0
for i,h in enumerate(hist):
    ans += i*h
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, X, M = map(int, readline().split())
ans = X
x = X
data = [0]*M
data[x] = 0
t = [x]
for i in range(1,N):
    nx = x ** 2 % M     
    if nx == 0:
        break
    if data[nx] != 0:
        res = N-i
        s = i-data[nx]
        syuki_cnt = res // s
        rem_cnt = res % s
        nt = t[data[nx]:i]
        ans += sum(nt)*syuki_cnt+sum(nt[:rem_cnt])
        break
    ans += nx
    x = nx
    data[nx] = i
    t.append(nx)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, X, M = list(map(int, input().split()))
    visited = [0] * M
    a = X
    path = list()
    while visited[a] == 0:
        visited[a] = 1
        path.append(a)
        a = (a**2) % M
    # ここのaは2度目なのでループの始端。
    # ループに入るまでの項数とループ長を求める。
    offset_size = 0
    for p in path:
        if p == a:
            break
        offset_size += 1
    loop_size = len(path) - offset_size
    # 後は、始端＋ループ＋最終ループに分けて、各値が何回出てくるか計算
    count = [0] * M
    n = 0
    # 始端
    for p in path[:offset_size]:
        count[p] += 1
        n += 1
        if n == N:
            break
    # ループ
    count_loop = (N - n) // loop_size
    for p in path[offset_size:]:
        count[p] += count_loop
        n += count_loop
    # 最後
    for p in path[offset_size:]:
        if n == N:
            break
        count[p] += 1
        n += 1
    print(sum([m * c for m, c in enumerate(count)]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
## coding: UTF-8

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

fresh = [True] * M #まだついたことのない場所をTrueにしている
fresh[X] = False
turn = [-1] * M #なん回目におとづれたか記録する
turn[X] = 0
status = True


#print(fresh, turn)

def search_loop():
    log = [X] #訪れた地点を記録するもの
    last  = X #最後に訪れた地点を記録するもの（ここから次に行くところを検索する）
    counter = 0
    loop_count = -1
    loop_start = -1
    while status:
        #next_spot = A[last - 1]
        next_spot = (last * last) % M 
        counter += 1
        #print(next_spot)
        if(fresh[next_spot]):
            #処理を書く
            log.append(next_spot)
            last = next_spot
            fresh[next_spot] = False
            turn[next_spot] = counter
        else:
            log.append(next_spot)
            last = next_spot
            fresh[next_spot] = False
            loop_count = counter - turn[next_spot]
            loop_start = turn[next_spot]
            #最後の人処理をする
            break
    #print(len())
    return log, last, turn, counter, loop_count, loop_start

#print(search_loop())

ret = search_loop()
#print(ret)
log = ret[0]
last = ret[1]
turn = ret[2]
counter = ret[3]
loop_count = ret[4]
loop_start = ret[5]
#print(log)
#print(loop_count)
#print(loop_start)

#print(log, last, turn)
#print(N, counter)
if(N <= len(log)):
    ans = sum(log[:N])
else:
    ans = sum(log[:loop_start])
    #ans = -1
    #print(log[loop_start:len(log)-1])
    sum_loop = sum(log[loop_start:len(log)-1])
    mawaru_kaisuu = (N-loop_start) // loop_count
    #print(mawaru_kaisuu)
    ans += (sum_loop * mawaru_kaisuu)
    nokori = (N-loop_start) - (loop_count*mawaru_kaisuu)
    ans += sum(log[loop_start:loop_start+nokori]) 


print(ans)

Submission status: Accepted

Solution code:
#import math
#import itertools
#import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
#MOD = 10 ** 9 + 7
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,x,m=INTM()
    bool=[False]*m
    mod=[]
    temp=x
    for i in range(m+1):
        if bool[temp]:
            break
        else:
            bool[temp]=True
            mod.append(temp)
            temp=(temp*temp)%m
    b=mod.index(temp)
    if b>0:
        sumt=sum(mod[0:b])
        mod=mod[b:]
    else:
        sumt=0
    lm=len(mod)
    sumr=0
    if (n-b)%lm!=0:
        sumr=sum(mod[0:(n-b)%lm])
    print(sumt+sumr+sum(mod)*((n-b)//lm))

if __name__=='__main__':
    do()

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
if M==1:
  print(0)
  exit()
lis = [0]*M
lis[0] = X
check = [-1]*M
check[X] = 0
for i in range(1,M):
  lis[i] = pow(lis[i-1],2,M)
  if check[lis[i]]>=0:
    cyc = i-check[lis[i]]
    start = check[lis[i]]
    break
  check[lis[i]] = i
from itertools import groupby, accumulate, product, permutations, combinations
cum = list(accumulate(lis))
cyc_cum = cum[-1]-cum[start]
if N-1<=start+cyc:
  ans = cum[N-1]
else:
  ans = cyc_cum*((N-1-start)//cyc)+cum[(N-1-start)%cyc+start]
print(ans)