Problem:


Score : 500 points

Problem Statement

Let us denote by f(x, m) the remainder of the Euclidean division of x by m.

Let A be the sequence that is defined by the initial value A_1=X and the recurrence relation A_{n+1} = f(A_n^2, M).
Find \displaystyle{\sum_{i=1}^N A_i}.

Constraints

1 \leq N \leq 10^{10}

0 \leq X < M \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X M

Output

Print \displaystyle{\sum_{i=1}^N A_i}.

Sample Input 1

6 2 1001

Sample Output 1

1369

The sequence A begins 2,4,16,256,471,620,\ldots Therefore, the answer is 2+4+16+256+471+620=1369.

Sample Input 2

1000 2 16

Sample Output 2

6

The sequence A begins 2,4,0,0,\ldots Therefore, the answer is 6.

Sample Input 3

10000000000 10 99959

Sample Output 3

492443256176507



Sample input:
6 2 1001


Sample output:
1369

Submission status: Wrong Answer

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

d = defaultdict(int)
data = defaultdict(int)
d2 = []
d2.append(x)

# d[x] = 1
cnt = 0
# data[x] = cnt
cnt += 1

for i in range(n):
    x = x**2 % m
    if d[x] == 1:
        st = data[x]
        cycle = cnt-st
        cycle_sum = sum(d2[st:])

        num_cycle = (n-st) // cycle
        amari = (n-st) % cycle

        # print(d2)
        # print(st, cycle, amari)

        print(num_cycle * cycle_sum + sum(d2[:st]) + sum(d2[st:st+amari]))
        sys.exit()
    else:
        d[x] = 1
        data[x] = cnt
        d2.append(x)
        cnt += 1

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
l=[x]
c=1
d=-1
f=0
while(x>1 and c<n):
    g=(x*x)%m
    d=g
    if(g in l):
        f=1
        break
    l.append(g)
    x=g
    c+=1
s=sum(l)
if(f==1):
    r=l.index(g)
    o=(n-c)//(c-r)
    t=(n-c)%(c-r)
    s+=o*(sum(l[r:]))+sum(l[r:r+t])
print(s)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

check = set()
hazimari = -1
owari = 0
y = x

check.add(x)
for i in range(n-1):
    owari = y
    y = y**2 % m
    if y in check:
        hazimari = y
        break
    check.add(y)

if hazimari == -1:#ループするまでもなくnが小さかったとき
    print(sum(check))
    exit()

ans = 0
count = 0
lp = []
y = x
for i in range(n-1):
    ans += y
    y = y**2 % m
    count = i+1
    if y == hazimari:
        lp.append(y)
        for j in range(n):
            y = y**2 % m
            lp.append(y)
            if y == owari:
                break
    else:
        continue
    break

ans += (n-2)//len(lp) * sum(lp)
ans += sum(lp[:(n-2)%len(lp)])
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n, x, m = map(int, input().split())
    inlis = list()
    inlis.append(x)
    mae = x
    kaisuu = 0

    for j in range(n-1):
        tsugi = mae ** 2 % m
        #print(tsugi)
        if tsugi not in inlis:
            inlis.append(tsugi)
            mae = tsugi
        else:
            inlis.append(tsugi)
            kaisuu = j+1
            bangou = inlis.index(tsugi)
            loop = len(inlis[bangou:-1])
            #print(kaisuu, bangou, loop)
            break
    #print(inlis)
    if kaisuu == 0:
        print(sum(inlis))
    else:
        loopnum = (n - bangou + 1) // loop
        amari = (n - bangou + 1) % loop
        if amari > 0:
            print(sum(inlis[:bangou])+loopnum*sum(inlis[bangou:-1])+sum(inlis[bangou:bangou+amari-1]))
        else:
            print(sum(inlis[:bangou])+loopnum*sum(inlis[bangou:-1]))

        



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(map(int, input().split()))

n, x, m = li()

tmp = x
l = [x]
begin = 0
for i in range(1, n):
    q = (tmp*tmp)%m
    if (q in l):
        begin = l.index(q)
        break
    l.append(q)
    tmp = q

ans = sum(l) if l[-1] == 0 else sum(l[:begin]) + n // len(l[begin:]) * sum(l[begin:]) + sum(l[begin: n % len(l[begin:])])

print(ans)

Submission status: Wrong Answer

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

A = [X]
Asum = [X]
roopsum = 0
ans = 0
index = 0
flag = 0

def f(x):
    global M
    global A
    global Asum
    if x == 1:
        return X
    else:
        A += [A[x-2]**2 % M]
        Asum += [Asum[x-2] + (A[x-2]**2 % M)]
        return A[x-2]**2 % M

for p in range(N):
    f(p+1)
    if A.count(A[p]) == 2: #A[p] in A:
        index = A.index(A[p])
        roop = p - index
        roopsum += Asum[p-1] - Asum[index-1]
        """
        for q in range(index(A[p]),p):
            roopsum += A[q]
        """
        ans += Asum[index-1]
        rooptimes = (N-1-index)//(p - index)
        roopamari = (N-1-index)%(p - index)
        ans += roopsum * rooptimes
        ans += Asum[index+roopamari] - Asum[index-1]
        flag = 1 #flag=1ならループがあった
        break
    
if flag == 0:
    ans += Asum[N-1]

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
p = [0 for i in range(m)]
p[x] = 1
k = x
ans = 0
ans += k
me = [k]
mem = [k]
fin = 0
for i in range(n-1):
    k = k**2%m
    if p[k] == 0:
        p[k] = i+2
        ans += k
        mem.append(k)
        me.append(ans)
    else:
        sp = k
        ss = i+2
        fin = 1
        break
if fin == 0:
    print(ans)
else:
    for i in range(m):
        if mem[i] == sp:
            spi = i+1
            break
    ans0 = me[spi-2]
    uu = ans - ans0
    ans0 += (n-spi+1)//(ss-spi)*uu
    for i in range((n-spi+1)%(ss-spi)):
        ans0 += mem[spi+i-1]
    print(ans0)

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
l=[x]
n-=1
f=-1
while(n>0):
    x=x*x
    x%=m
    if x in l:
        for i in range(len(l)):
            if x==l[i]:
                f=i
                s=l[i:].copy()
                break
    if f!=-1:
        break
    l.append(x)
    n-=1

if n==0:
    print(sum(l))
else:
    ans=sum(l)
    l=s.copy()
    print(l,s)
    ans+=sum(l)*(n//len(l))
    c=n%len(l)
    f=0
    while(c!=0):
        ans+=l[f]
        c-=1
        f+=1
    print(ans)

Submission status: Wrong Answer

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

a = [x]
while True:
  res = (a[-1]**2) % m
  if len(a) == n:
    print(sum(a))
    sys.exit()
  elif res == 0:
    print(sum(a))
    sys.exit()
  elif res in a:
    ai = a.index(res)
    aa = a[ai:]
    break
  else:
    a.append(res)

if len(a) >= n:
  print(sum(a[:n]) )
  sys.exit()

shuuki = len(aa)
shuuki_sum0 = sum(a[:ai])
shuuki_sum = sum(aa)

ans = shuuki_sum0 + shuuki_sum * ( (n-len(a)) // shuuki ) + sum( aa[:(n-len(a)) % shuuki] )
print(ans)

Submission status: Wrong Answer

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

ans = x
d = defaultdict(int)
data = defaultdict(int)
d2 = []
d2.append(x)

# d[x] = 1
cnt = 0
data[x] = cnt
cnt += 1

for i in range(n):
    x = x**2 % m
    if d[x] == 1:
        st = data[x]
        cycle = cnt-st
        cycle_sum = sum(d2[st:])

        num_cycle = (n-st) // cycle
        amari = (n-st) % cycle

        # print(d2)
        # print(st, cycle, amari)

        print(num_cycle * cycle_sum + sum(d2[:st]) + sum(d2[st:st+amari]))
        sys.exit()
    else:
        d[x] = 1
        data[x] = cnt
        d2.append(x)
        cnt += 1

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
ans=x
totol=n
was=[0]*m
was[x]=1
cs=x
cr=1
n-=1
seq=[x]
while n>0:
	cs=cs*cs%m
	seq.append(cs)
	cr+=1
	n-=1
	if was[cs]:
		if cs<=1:exit(print(ans+cs*(n+1)))
		res=sum(seq[:was[cs]-1])
		totol-=was[cs]-1
		loop=cr-was[cs]
		sumonloop=sum(seq[was[cs]:cr])
		res+=totol//loop*sumonloop
		for i in range(totol%loop-1):
			cs=cs*cs%m
			res+=cs
		exit(print(res))
	else:was[cs]=cr
	ans+=cs
print(ans)
'''
10 2 6

38

'''

Submission status: Wrong Answer

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

result = [x]
pat = set()
pat.add(x)
flg = False
for _ in range(n):
    tmp = pow(result[-1], 2, m)
    if tmp in pat:
        flg = True
        break
    elif tmp == 0:
        result.append(tmp)
        print(sum(result))
        sys.exit()
    else:
        result.append(tmp)
        pat.add(tmp)
        
if not flg:
    print(sum(result))

else:
    cnt = result.index(tmp)
    cycle = result[-(len(result) - cnt):]
    rest = (n - cnt)
    print(sum(result[:cnt]) + (rest // len(cycle)) * sum(cycle) + sum(cycle[:rest % len(cycle)]))

Submission status: Wrong Answer

Solution code:
import sys

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

    S = [0] * M  # 何回目に来たか
    C = [0] * M  # 最初にたどり着いたときの値

    _sum = 0
    cycle_sum = 0
    cycle_count = 0
    for i in range(1, N+1):
        _sum += X
        if S[X] == 0:
            C[X] = _sum
            S[X] = i
        else:
            cycle_sum = _sum - C[X]
            cycle_count = i - S[X]
            break
        X = X**2 % M
    else:
        print(_sum)
        return        

    # print(X, S[X], C[X])
    first_sum = C[X]
    loop = (N - S[X]) // cycle_count
    loop_sum = loop * cycle_sum
    _sum = first_sum + loop_sum
    rest = (N - S[X] + 1)  % cycle_count
    # print(first_sum, loop, cycle_count,cycle_sum, loop_sum, rest)
    # print(X)

    for i in range(rest):
        _sum += X
        X = X**2 % M
    
    print(_sum)


main()

Submission status: Wrong Answer

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

lis=[0]*m

ans=x
ai=x
lis[ai]=[1,ans]
flg=0

for i in range(2,n+1):
    ai=(ai**2)%m
    if lis[ai]!=0:
        start=lis[ai][0]
        goal=i-1
        span=goal-start+1
        sumspan=ans-lis[ai][1]+ai
        flg=1
        if sumspan==1:
            ans-=1
        break
    ans+=ai
    lis[ai]=[i,ans]

if flg:
    times=(n-goal)//span
    last=(n-goal)%span-1
    ans+=sumspan*times
    #print(times)
    #print(sumspan*times)
    ans+=ai
    for i in range(last):
        ai=(ai**2)%m
        ans+=ai
    print(ans)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    N, X, M = map(int, input().split())

    A = X
    ans = 0
    loop = set([A])
    lst = [A]
    for _ in range(N):
        ans += A
        A = pow(A, 2, M)
        if A in loop:
            loop_start = lst.index(A)
            loop_sum = sum(lst[loop_start:])
            loop_length = len(lst[loop_start:])
            a = sum(lst[:loop_start])
            b = loop_sum * ((N - loop_start) // loop_length)
            c = sum(lst[loop_start:((N - loop_start) % loop_length) + 2])
            ans = a + b + c
            break
        else:
            loop.add(A)
            lst.append(A)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#E
n,x,m = map(int,input().split())
X = x
seen = set()
seen.add(x)
lst = []
lst.append(x)
cnt = 1
num = []
num.append(x)
def cycle(x,x1,idx):
  first =lst.index(x)
  amari = (n-cnt)%(idx-first)
  cyclenum = (n-cnt)//(idx-first)
  ans = cyclenum*(num[idx-1]-num[first-1])
  if amari != 0:
    ans += x1
    for i in range(amari-1):
      x1 = x1**2 %m
      ans += x1
  if first != 0:
      ans += num[first]
  return ans
 

for i in range(1,n):
  x = x**2 %m
  if x in seen:
    print(cycle(x,X,i))
    exit()
    
  else:
    seen.add(x)
    lst.append(x)
    cnt += 1
    num.append((x+num[i-1]))
print(num[-1])

Submission status: Wrong Answer

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

lim = 10**5*2+1

f = [0]*(lim)
a = [0]*(lim)

x = X
f[x] = 1
a[1] = x

ans = x

i = 1
l = N
while i < l:
    i += 1

    x **= 2
    x %= M
    if not x:
        break

    if f[x]:
        lp_len = (i-f[x])
        z = (l-i+1)//lp_len
        if z:
            ls = ans - a[f[x]-1]
            ans += ls * z
            i += z*lp_len

    ans += x
    
    f[x] = i
    if i < lim:
        a[i] = ans

print(ans)

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
# 一定回数を経ると循環するので最後にかければよい
loop=list()
app = [0]*m
last = -1
a_i = x
while 1:
  a_i = (a_i**2)%m
  if a_i in (0,1) or app[a_i]:
    # あまりが0か1になったらそのあとはずっと一緒
    # もしくはloopの端にきたらloop開始
    last = a_i
    break
  else:
    loop.append(a_i)
    app[a_i] = len(loop)
    if len(loop) > n-2:
      break
# 答の計算
ans=x
if last < 2:
  ans += sum(loop)
  if last > -1:
    ans += last * (n - 1 - len(loop))
else:
  # ループの端までは普通に足す
  ans += sum(loop[:app[last]-1])
  #print(ans)
  # ループの中を累計で足す
  ans += sum(loop[app[last]-1:]) * ((n-1) // (len(loop)-app[last]+1))
  #print(ans)
  # 余りを足す
  ans += sum(loop[app[last]-1:((n-1) % (len(loop)-app[last]+1))])
print(ans)
#print(*loop)

Submission status: Wrong Answer

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

a = [x]
while True:
  res = (a[-1]**2) % m
  
  if len(a) == n:
    print(sum(a))
    sys.exit()
  elif res == 0:
    print(sum(a))
    sys.exit()
  elif res in a:
    ai = a.index(res)
    aa = a[ai:]
    break
  else:
    a.append(res)

if len(a) >= n:
  print(sum(a[:n]) )
  sys.exit()

shuuki = len(aa)
shuuki_sum0 = sum(a[:ai])
shuuki_sum = sum(aa)

ans = shuuki_sum0 + shuuki_sum * ( (n-len(a)) // shuuki ) + sum( aa[:(n-len(a)) % shuuki] )
print(n%shuuki)
print(ans)

Submission status: Wrong Answer

Solution code:
n,x,mod=map(int,input().split())
#32 回やればコーナーは回避できる
now=x
xs=0
for i in range(min(n,32)):
    if now%mod==0:print(xs);exit()
    else:
        xs+=now
        now=now*now%mod
        
if x%mod:
    from collections import defaultdict
    d=defaultdict(int)
    su=defaultdict(int)
    s=0
    for i in range(1,n+1):
        if  d[x]:cnt=i;pre=d[x];break
        d[x]=i
        s+=x
        su[i]=s
        x=x**2%mod
    else:print(s);exit()
    length=cnt-pre
    roop=(n+1-pre)//length
    amari=(n+1-pre)%length
    once=s-su[pre]+x

    print(su[pre]+roop*once+su[pre+amari-1]-su[pre-1])


else:print(0)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.buffer.readline

n, x, mod = map(int, input().split())
ans = 0
temp = x
num = 1
while temp < mod:
    temp *= x
    num += 1


A = [0] * (mod + 1)

if temp == mod:
    A[1] = x % mod
    ans += A[1]
    for i in range(2, num + 1):
        A[i] = A[i - 1] * A[i - 1] % mod
        ans += A[i]
        # print(ans)
    print(ans)
    exit()

kouho = {}
if n < mod:
    A[1] = x % mod
    ans += A[1]
    for i in range(2, n + 1):
        A[i] = A[i - 1] * A[i - 1] % mod
        ans += A[i]
        # print(ans)
else:
    A[1] = x % mod
    ans += A[1]
    kouho[A[1]] = 1
    for i in range(2, 2 * mod + 1):
        A[i] = A[i - 1] * A[i - 1] % mod
        if A[i] in kouho:
            migi = i
            break
        ans += A[i]
        kouho[A[i]] = i
    saisho = ans
    hidari = kouho[A[i]]
    cycle_val = 0
    for i in range(hidari, migi):
        cycle_val += A[i]
    cycle = migi - hidari
    kaisu = n // cycle
    amari = n % cycle
    if hidari + kaisu * cycle + amari > n:
        kaisu -= 1
    amari_val = 0
    for i in range(1, amari + 1):
        amari_val += A[i]
    ans = saisho + cycle_val * kaisu + amari_val
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def naive(N, X, M):
    ans = X
    ans_prev = X
    for i in range(2, N + 1):
        an1 = ans_prev % M
        an1 = pow(an1, 2, M)
        ans += an1
        ans_prev = an1
    return ans

def doubling(N, X, M):
    ans = X
    ans_prev = X
    A = [X]
    computed = set({})

    for i in range(2, N + 1):
        an1 = ans_prev % M
        an1 = pow(an1, 2, M)
        if an1 in computed:
            breakA = an1
            break
        A.append(an1)
        computed.add(an1)
        ans_prev = an1

    # if break
    num_break = len(A)
    index = A.index(breakA)
    num_length = len(A) - index
    total = sum(A[:index])    
    repeat_length = (N - index) // num_length
    remain_length = (N - index) % num_length
    total_sub = sum(A[index:]) * repeat_length
    sub = naive(remain_length, breakA, M)
    total += total_sub + sub
    return total


def solve(N, X, M):
    return -1

def main():
    from builtins import int, map
    N, X, M = map(int, input().split())

    if N < 10 ** 7:
        print(naive(N, X, M))
    else:
        print(doubling(N, X, M))
        # print(naive(N, X, M))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
dp = [0 for i in range(n)]
dp[0] = x
res = 0
for i in range(1,n):
    dp[i] = dp[i-1] * dp[i-1]
    if dp[i] >= m:
        dp[i] = dp[i]%m
    res += dp[i]
print(res)

Submission status: Wrong Answer

Solution code:
import copy

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

visited = [-1]*(m+1)
when = [-1]*(m+1)
ans = 0
i = 1
while i <= n:
    ans += x
    if x == 0:
        break
    if visited[x] > -1:
        cycle = (n - i) // (i - when[x])
        ans += cycle*(ans - visited[x])
        i += cycle*(i - when[x])
        visited = [-1]*(m+1)
        when = [-1]*(m+1)
        x **= 2
        x %= m    
        continue
    visited[x] = copy.deepcopy(ans)
    when[x] = copy.deepcopy(i)
    x **= 2
    x %= m
    i += 1


print(ans)

Submission status: Wrong Answer

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

lim = 10**5+1

f = [0]*(lim)
a = [0]*(lim)

x = X
f[x] = 1
a[1] = x

ans = x

i = 1
l = N
while i < l:
    i += 1

    x **= 2
    x %= M
    if not x:
        break

    if f[x]:
        lp_len = (i-f[x])
        z = (l-i+1)//lp_len
        if z:
            ls = ans - a[f[x]-1]
            ans += ls * z
            i += z*lp_len

    if i < l:
        ans += x
    
    f[x] = i
    if i < lim:
        a[i] = ans

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n,x,m = map(int,input().split())
    if m == 0:
        print(0)
        return
    t = [x]
    k = -1
    for _ in range(n):
        x = x**2 % m
        if x in t:
            k = x
            break
        t.append(x)
    if k not in t:
        print(sum(t))
        return
    else:
        s = t.index(k)
        ans = sum(t[0:s])
        b = t[s:len(t)]
        n -= s
        ans += sum(b) * (n//len(b))
        ans += sum(b[0:n%len(b)])
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
dic = defaultdict(int)
N, X, M = map(int, input().split())
A = [X]
ans = X
fir = -1
if N>1:
    temp = 1
    dic[X]=temp
    for i in range(2, N+1):
        a = A[-1]*A[-1]%M
        if dic[a]>0:
            fir = dic[a]
            break
        A.append(a)
        ans+=a
        temp+=1
        dic[a]=temp
    if fir!=-1:
        T = temp-fir+1#周期
        Tsum = 0 #周期の和
        TempSum = 0 #後半あまりの和
        M=N-fir+1 # 先頭のぞく 
        amari = M%T # 後半あまり
        for k in dic:
            if dic[k]>=fir and dic[k]<=temp:
                Tsum+=k
            if dic[k]>=fir and dic[k]<fir+amari:
                TempSum += k
        ans+=TempSum
        ans+=Tsum*(M//T-1)
        print(dic)
    print(ans)
else:
    print(ans)

Submission status: Wrong Answer

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

Visited = [0]*(M+1)
latestvisit = [0]*(M+1)
count = 0

latest = 0
        
for i in range (0, N):
	if Visited[X] > 0:
		latest = X
		latestvisit[X] = i
		break
	latestvisit[X] = i
	Visited[X]+= 1
	X = (X**2)%M

P = sum(Visited)

for j in range (0, M+1):
	count+=(j*Visited[j])

Submission status: Wrong Answer

Solution code:
N,X,M=map(int,input().split())
total=0
a=X
i=1
while i<N+1 :
  total=total+a
  a=(X*X)%M
  i=i+1
else:
  print(total)

Submission status: Wrong Answer

Solution code:
l=input().split()
n=int(l[0])
x=int(l[1])
m=int(l[2])
hashi=dict()
pref=0
count=0
prefix=[]
for i in range(n):
    if(i==0):
        ans=x%m
    else:
        ans=ans*ans
        ans%=m
    if(ans in hashi):
        period=i-(hashi[ans][0])
        num1=hashi[ans][0]
        k=(n-num1)//period
        rem=(n-(num1+k*period))
        count=count+prefix[rem]
        count=count+k*(pref-hashi[ans][1])
        for j in range(rem):
            if(j!=0):
                ans=ans*ans
            ans%=m
            count+=ans
        break
    hashi[ans]=(i,pref)
    prefix.append(pref)
    pref+=ans
print(max(pref,count))

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,x,m=nii()

ans=x
x_list=[x]
for i in range(n-1):
  a=(x**2)%m
  ans+=a
  x=a
  if x in x_list:
    zan=(n-1)-i
    break
  else:
    x_list.append(x)


print(ans)

Submission status: Wrong Answer

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

result = [x]
pat = set()
pat.add(x)
flg = False
for _ in range(n):
    tmp = pow(result[-1], 2, m)
    if tmp in pat:
        flg = True
        break
    else:
        result.append(tmp)
        pat.add(tmp)
        
if not flg:
    print(sum(result))

else:
    cnt = result.index(tmp)
    cycle = result[-(len(result) - cnt):]
    rest = (n - cnt)
    print(sum(result[:cnt]) + (rest // len(cycle)) * sum(cycle) + sum(cycle[:rest % len(cycle)]))

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
an = x
ans = 1
i = 1
while i <= n:
    an_1 = an**2 % m
    ans += an_1
    an = an_1
    i += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
A = X
T = [A]
ans = A

for n in range(N - 1):
  tmp = A ** 2 % M
    
  if tmp in T:
    pre_tmp_idx = T.index(tmp)
    syuki = T[pre_tmp_idx:]
    
    len_syuki = len(syuki)
    
    nokori_syuki = (N - n) // len_syuki
    
    syuki_amari = (N - n) % len_syuki
    
    ans += sum(syuki) * nokori_syuki + sum(syuki[:syuki_amari-1])
    break

  ans += tmp
  A = tmp
  T.append(tmp)
    
print(ans)

Submission status: Wrong Answer

Solution code:
def kai(N, X, M):
    A_n = [X]
    for i in range(1, N):
        A_i = (A_n[i-1] **2) % M
        A_n.append(A_i)
    return A_n, sum(A_n)

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

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
# 一定回数を経ると循環するので最後にかければよい
loop=list()
app = [0]*m
last = -1
a_i = x
while 1:
  a_i = (a_i**2)%m
  if a_i in (0,1) or app[a_i]:
    # あまりが0か1になったらそのあとはずっと一緒
    # もしくはloopの端にきたらloop開始
    last = a_i
    break
  else:
    loop.append(a_i)
    app[a_i] = len(loop)
    if len(loop) > n:
      break
# 答の計算
ans=x
if last > -1:
  ans += sum(loop) + last * (n - 1 - len(loop))
else:
  # ループの端までは普通に足す
  ans += sum(loop[:app[last]-1])
  #print(ans)
  # ループの中を累計で足す
  ans += sum(loop[app[last]-1:]) * ((n-1) // (len(loop)-app[last]+1))
  #print(ans)
  # 余りを足す
  ans += sum(loop[app[last]-1:((n-1) % (len(loop)-app[last]+1))])
print(ans)
#print(*loop)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
appear = [False] * m
r = [x]
appear[x] = True
a = x
i = 1
while True:
    a = (a * a) % m
    if appear[a]:
        break
    else:
        appear[a] = True
        r.append(a)
        i += 1
        if i == n:
            print(sum(r))
            exit()
cycle_len = len(r)
print(cycle_len)
ans = sum(r) * (n // cycle_len) + sum(r[:(n % cycle_len)])
print(ans)

Submission status: Wrong Answer

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

dp = [-1 for _i in range(10**5+2)]
nums = [-1 for _i in range(10**5+2)]
nums[x] = 1

dp[x] = x
bef = x
nex = (x**2)%m
r = [0, x]
while dp[nex] < 0:
    nums[nex] = nums[bef]+1
    dp[nex] = dp[bef]+nex
    r.append(dp[nex])
    nex, bef = (nex**2)%m, nex

if nex == 0:
    print(r[min(len(r)-1, n)])
if n <= nums[bef]:
    print(r[n])
else:
    roop = nums[bef] - nums[nex] + 1
    roop_value = r[nums[bef]] - r[nums[nex] - 1]
    plus = r[nums[nex]-1]*(n>=nums[nex]+1)
    n = max(0, n-nums[nex]+1)
    print(
        roop_value*(n//roop)+plus+
        r[n%roop + nums[nex] -1]
        -r[nums[nex] - 1]
    )

Submission status: Wrong Answer

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

lim = 10**5+1

f = [0]*(lim)
a = [0]*(lim)

x = X
f[x] = 1
a[1] = x

ans = x

i = 1
l = N
while i < l:
    i += 1

    x **= 2
    x %= M
    if not x:
        break

    if f[x]:
        lp_len = (i-f[x])
        z = (l-i+1)//lp_len
        if z:
            ls = ans - a[f[x]-1]
            ans += ls * z
            i += z*lp_len

    ans += x
    
    f[x] = i
    if i < lim:
        a[i] = ans

print(ans)

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
tmp=x
L=[]
Flag=False
for i in range(n):
    tmp=tmp**2%m
    if tmp==0:
        Flag=True
        break
    elif tmp not in L:
        L.append(tmp)
    else:
        break
if Flag:
    ans=x+sum(L)
else:
    times=(n-len(L))//len(L)
    loss=(n-len(L))%len(L)
    ans=x+sum(L)*times
    for i in range(loss):
          ans+=L[i]
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n,x,m = map(int,input().split())
    R = [x]
    g = set([x])
    for i in range(1,min(m,n)):
        x = x**2 % m
        if not x in g:
            R.append(x)
            g.add(x)
        else:
            break
    
    R_ac = [0]*len(R)
    R_ac[0] = R[0]
    for i in range(1,len(R)):
        R_ac[i] = R_ac[i-1] + R[i]

    j = R.index(x)
    ct = n
    
    ans = R_ac[j-1]
    ct-=j

    q = ct//(len(R)-j)
    ans+= q*(R_ac[-1]-R_ac[j-1]) 
    ct-=q*(len(R)-j)

    ans+= R_ac[j-1+ct] - R_ac[j-1]

    print(ans)
main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
# 一定回数を経ると循環するので最後にかければよい
loop=list()
app = [0]*m
last = -1
a_i = x
while 1:
  a_i = (a_i**2)%m
  if a_i in (0,1) or app[a_i]:
    # あまりが0か1になったらそのあとはずっと一緒
    # もしくはloopの端にきたらloop開始
    last = a_i
    break
  else:
    loop.append(a_i)
    app[a_i] = len(loop)
    if len(loop) > n:
      break
# 答の計算
ans=x
if last < 1:
  ans += sum(loop) + last * (n - len(loop) - 1)
else:
  # ループの端までは普通に足す
  ans += sum(loop[:app[last]-1])
  #print(ans)
  # ループの中を累計で足す
  ans += sum(loop[app[last]-1:]) * ((n-1) // (len(loop)-app[last]+1))
  #print(ans)
  # 余りを足す
  ans += sum(loop[app[last]-1:((n-1) % (len(loop)-app[last]+1))])
print(ans)
#print(*loop)

Submission status: Wrong Answer

Solution code:
import sys

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

    S = [0] * M  # 何回目に来たか
    C = [0] * M  # 最初にたどり着いたときの値

    _sum = 0
    cycle_sum = 0
    cycle_count = 0
    for i in range(1, N+1):
        _sum += X
        if S[X] == 0:
            C[X] = _sum
            S[X] = i
        else:
            cycle_sum = _sum - C[X]
            cycle_count = i - S[X]
            break
        X = X**2 % M
    else:
        print(_sum)
        return        

    # print(X, S[X], C[X])
    first_sum = C[X]
    loop = (N - S[X] + 1) // cycle_count
    loop_sum = loop * cycle_sum
    _sum = first_sum + loop_sum
    rest = (N - S[X] + 1)  % cycle_count
    # print(X)

    for i in range(rest):
        _sum += X
        X = X**2 % M
    
    print(_sum)


main()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ans = 0

check = np.zeros(M+1, dtype = int)
suuretu = []

#print(check)

for i in range(N):
    if(check[X] == 1):
        detatoko = suuretu.index(X)
        loop_sum = sum(suuretu[detatoko:])
        loop_kaisu = i - detatoko
#        print(loop_sum, loop_kaisu)

        plus_kaisu = (N - i - 1) // loop_kaisu
        mod_plus = (N - i) % loop_kaisu

#        print(plus_kaisu, mod_plus)
        ans += loop_sum * plus_kaisu
        ans += sum(suuretu[detatoko:detatoko+mod_plus])
        break


    else:
        check[X]  = 1

    ans += X
    suuretu.append(X)

    if(X == 0):
        break

    if(X == 1):
        ans += N - 1 - i
        break
    X = (X * X) % M

#print(check)
print(ans)
#print(suuretu)

Submission status: Wrong Answer

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

n = int(n)
x = int(x)
m = int(m)

total = x
prev_a = x
used_mod_list = [x]
roop_flag = False

for i in range(1, n):
  a = prev_a ** 2 % m
  if a == 0:
    break
  elif a in used_mod_list:
    roop_flag = True
    roop_index = i
    break
  else:
    total += a
    prev_a = a

if roop_flag:
  roop_num = n // (i+1)
  total = total * roop_num
  rest = roop_num % (i+1)
  total += sum(used_mod_list[:rest])
    
print(total)

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
a_n = x
ans = 0
i = 1
while i <= n:
    an_1 = a_n**2 % m
    ans += an_1
    a_n = an_1
    i += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,X,M=map(int,input().split())
l=[-1]*M
a=0
t=X
l[X]=0
if t**2%M==t:
    print(N*t)
    exit()
for i in range(1,M+1):
    t=t**2%M
    if l[t]==-1:
        l[t]=i
    else:
        s,g=l[t],i
        break
if N<=s+1:
    t=X
    a=X
    for i in range(N-1):
        t=t**2%M
        a+=t
    print(a)
else:
    t=X
    a=X
    for i in range(s-1):
        t=t**2%M
        a+=t
    t2=t
    c=0
    for i in range(g-s):
        t=t**2%M
        c+=t
    for i in range((N-s)%(g-s)):
        t2=t2**2%M
        a+=t2
    a+=c*((N-s)//(g-s))
    print(a)

Submission status: Wrong Answer

Solution code:
while True:
    try:
        n,x,m = map(int,input().split())
        print(n,x,m)
        prev = x
        ans = x
        for i in range(1,n):
            ans += (prev**2)%m
            prev = (prev**2)%m
        
        #print(ans)
    except:
        break

Submission status: Wrong Answer

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

rec = []
s = set()
rec.append(X)
s.add(X)
r = X
idx = -1
idx1 = -1
for i in range(N+1):
    r = (r**2)%M
    if(r not in s):
        rec.append(r)
        s.add(r)
    else:
        rec.append(r)
        idx = i+1
        break
    
for i in range(len(rec)):
    if(rec[i] == rec[idx]):
        idx1 = i
        break

if(idx == -1 and idx1 == -1):
    print(sum(rec))
elif(idx1 != idx):       
    ans = sum(rec[:idx1])
    ans += sum(rec[idx1:idx])*((N-idx1)//(idx-idx1))+sum(rec[idx1:(idx1+(N-idx1)%(idx-idx1))])
    print(ans)
else:
    ans = sum(rec[:idx1])
    ans += rec[idx]*(N-idx1)
    print(ans)