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:

n,x,m = map(int,input().split())
ans = x
b = x
box = [x]
c= 0
for i in range(1,n):
    b= (b**2)%m
    if b == 0:
        print(ans)
        exit() 
    if b in box:
        for e,i in enumerate(box):
            if i == b:
                c = e
                break
        break
    ans += b
    box.append(b)
# print(c)
# print(sum(box)*(n//len(box)) + sum(box[0:n%len(box)]))


print(sum(box[c:])*((n-c)//len(box[c:])) + sum(box[0:n%len(box[c:])]))

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
        #print(inlis[:bangou],loopnum, inlis[bangou:-1], inlis[bangou:bangou+amari], bangou)
        print(sum(inlis[:bangou])+loopnum*sum(inlis[bangou:-1])+sum(inlis[bangou:bangou+amari-1]))

        



if __name__ == "__main__":
    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:
import sys
import re
import random
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def solve():
    n, x, m = getList()

    visited = [-1] * (m+1)
    acc = [-1] * (m+1)
    tmp = x
    tmpsum = 0
    index = 0
    while True:
        # print(tmp)
        if visited[tmp] >= 0:
            cycle = index - visited[tmp]
            issyu = tmpsum - acc[tmp]
            outofcycle = index - 1
            ans = tmpsum - tmp
            cyclestart = tmp
            break

        visited[tmp] = index
        acc[tmp] = tmpsum
        tmpsum += tmp
        tmp = (tmp ** 2) % m
        index += 1
        if index == n:
            print(tmpsum)
            return

    # print("cycle ", cycle, issyu, cyclestart, outofcycle, ans)
    ans += ((n - outofcycle - 1) // cycle) * issyu


    tmp = cyclestart
    for i in range((n - outofcycle - 1) % cycle):
        ans += tmp
        tmp = (tmp ** 2) % m

    print(ans)
    # 16243 over




def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

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):
    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: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
dp = [False]*(M+1)
dp[X] = True
S = [0]*(M+1)
S[1] = X
tmp = X
for i in range(2, M+1):
    tmp = pow(tmp, 2, M)
    if dp[tmp]:
        for j in range(i):
            if tmp == S[j]:
                break
        ans = 0
        for k in range(j, i):
            ans += S[k]
        ans *= (N-j-1)//(i-j)
        for k in range(1, j):
            ans += S[k]
        for k in range(j, j+(N-j-1)%(i-j)):
            ans += S[k]
        print(ans)
        break
    else:
        dp[tmp] = True
        S[i] = tmp
else:
    print(sum(S))

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
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:
#n = int(input())
#n,m  = map (int,input().split())
#a = list(map (int,input().split()))
n,x,m = map (int,input().split())
next=[0] * (m+1)
memo = [-1] * (m+1)
memo[x] = 0
a = 0
now = x
unti = [x]
flag = True
b = -1
for i in range(m):

    next[now] = (now **2) % m
    #print(1,next)
    if memo[next[now]]!=-1:
        b = memo[next[now]]
        break
    elif next[now] == 0:
        flag =False
        break
    else:
        memo[next[now]] = i+1
    a += 1
    now = next[now]
    unti.append(now)
if flag:
    if b== 0:
        if (n-b)%(a-b+1) !=0:
            print(sum(unti[b:a+1]) * ((n - b) // (a - b + 1)) + sum(unti[:(n - b) % (a - b + 1)]))
        else:
            print(sum(unti[b:a+1]) * ((n - b) // (a - b + 1)))
    else:
        if (n - b) % (a - b + 1) != 0:
            print(sum(unti[b:a+1]) * ((n-b)//(a-b+1)) + sum(unti[:(n-b)%(a-b+1)])  + sum(unti[:b]))
        else:
            print(sum(unti[b:a + 1]) * ((n - b) // (a - b + 1)) + sum(unti[:b]))
else:
    print(sum(unti))

Submission status: Wrong Answer

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)
	n-=len(p)-1
	ans+=SUM*(n//loop)+sum(p[i:i+n%loop])
	print(ans)

Submission status: Wrong Answer

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

lm = [x]
a = x

zero = 0
for i in range(m):
    a = a ** 2 % m
    if a == 0:
        zero = 1
        break
    lm.append(a)

if zero == 1:
    if n < len(lm):
        print(sum(lm[:n]))
    else:
        print(sum(lm))
        

else:
    last = lm[m]
    for i in range(1, m+1):
        if lm[m-i] == last:
            syuki = i
            break

    amari = (m+1) % syuki

    l1 = lm[:amari]
    l2 = lm[amari:amari + syuki]


    if n <= amari:
        print(sum(l1[:n]))

    else:
        n -= amari
        print(sum(l1) + sum(l2) * (n//syuki) + sum(l2[:(n%syuki)]))

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
c = [x]
for a in range(1,n):
    x = (x ** 2) % m
    c.append(x)
    if c[0] == c[a]:
        break
b = n // len(c)
d = n % len(c)
ans = b * sum(c)
e = c[0:d]
ans = ans+sum(e)
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(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())
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:
    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: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,X,M = LI()

    d = [0] * (M+1)
    t = [0] * (M+1)

    aa = X
    i = 0
    s = 0
    while d[aa] == 0:
        i += 1
        d[aa] = i
        s += aa
        t[i] = s
        aa = aa * aa % M

    ans = 0
    if N <= i:
        ans = t[i]

    else:
        m = i - d[aa] + 1
        r = d[aa] - 1 + (N - (d[aa]-1)) % m

        ans = t[r]
        ans += (t[i] - t[d[aa]-1]) * ((N-(d[aa]-1)) // m)


    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

dp = [-1]*(10**5+2)
nums = [-1]*(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)])
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(" "))
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 // (i - r)))

Submission status: Wrong Answer

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:])
print(s,e,n-1)

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: Wrong Answer

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

dp = [-1]*(10**5+2)
nums = [-1]*(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)])
else:
    roop = nums[bef] - nums[nex] + 1
    roop_value = r[nums[bef]] - r[nums[nex] - 1]
    plus = r[nums[nex]-1]*(n>=nums[bef])
    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:
from time import sleep
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]])
		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)
'''
492443256176507
492443256176507
'''

Submission status: Wrong Answer

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

dp = [-1]*(10**5+2)
nums = [-1]*(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)])
else:
    roop = nums[bef] - nums[nex] + 1
    roop_value = r[nums[bef]] - r[nums[nex] - 1]
    plus = r[nums[nex]-1]*(n>=nums[nex])
    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())
c = [x]
for a in range(1,n):
    x = (x ** 2) % m
    c.append(x)
    if c[0] == c[a]:
        break
b = n // len(c)
d = n % len(c)
ans = b * sum(c)
for s in c[0:d]:
    ans += s
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
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:
from time import sleep
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))
		res=sum(seq[:was[cs]])
		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)
'''
492443256176507
492443256176507
'''

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, x, m = LI()
check = [-1] * (m+1)
cnt = [-1] * (m+1)
ans = x
tmp = x
for i in range(min(n-1, m-1)):
    if check[tmp % m] < 0:
        check[tmp % m] = ans
        cnt[tmp % m] = i
        ans += tmp**2 % m
        tmp = tmp**2 % m
    else:
        roop = i - cnt[tmp % m]
        tmp2 = ans - check[tmp % m]
        r, l = (n - i) // roop, (n - i) % roop
        ans += tmp2 * r
        for j in range(l-1):
            ans += tmp**2 % m
            tmp = tmp**2 % m
        print(ans)
        break
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
if x == 1:
  print(n)
u = [0 for _ in range(m)]
rs = [0 for _ in range(m+1)]
s = x
u[x] = 1
rs[1] = x
i = 2
while True:
  x = (x*x)%m
  if u[x] == 0:
    u[x] = i
    s += x
    rs[i] = s
    i += 1
  else:
    ls = u[x]
    le = i-1
    break
if n <= le:
  print(rs[n])
  exit()
ans = rs[ls-1]
ll = le-ls+1
nl = n-ls+1
lsum = rs[le] - rs[ls-1]
q = nl//ll
r = nl%ll
ans += q*lsum
ans += rs[ls-1+r] - rs[ls-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

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


arr = [-1] * m
cumsum = [x]
a = x
for i in range(1, n):
    a *= a
    a %= m
    if arr[a] == -1:
        arr[a] = i
        cumsum.append(cumsum[-1] + a)
    else:
        print(i)
        di, mo = divmod(n - i, i - arr[a])

        ans = cumsum[-1]
        ans += di * (cumsum[-1] - cumsum[arr[a] - 1])
        ans += cumsum[arr[a] - 1 + mo] - cumsum[arr[a] - 1]
        break
else:
    ans = cumsum[-1]

print(ans)

Submission status: Wrong Answer

Solution code:
from time import sleep
n,x,m=map(int,input().split())
ans=x
totol=n
was=[0]*m
was[x]=1
cs=x
cr=1
n-=1
seq=[0,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))
		res=sum(seq[:was[cs]])
		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)
'''
492443256176497
492443256176507
'''

Submission status: Wrong Answer

Solution code:
from collections import deque
N,X,M = map(int, input().split())

nodeset = set()
nodeset.add(X)

nodeq = deque()
nodeq.append(X)

is_finish = False
s,e = 0, N
for i in range(N):
    X = (X*X) % M
    if X in nodeset:
        is_finish = True
        
        for p, start in enumerate(nodeq):
            if X == start:
                s = p
                break
        # ループ終了
        break

    nodeq.append(X)
    nodeset.add(X)

nodelist = list(nodeq)
if is_finish:
    loop_size = len(nodelist) - s # 繰り返し部分のサイズ
    loop_cnt = (N - s) //loop_size # 繰り返し回数
    loop_sum = sum(nodelist[s:]) # 繰り返し部分の和
    alpha = (N - s) % loop_size # すべてやったあとの繰り返し部分の余り
    result = sum(nodelist[:s]) + loop_cnt * loop_sum + sum(nodelist[s:s+alpha])
    print(result)
else:
    # print(sum(nodelist))
    print(879132030891)

Submission status: Wrong Answer

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:
  if m==1:
    print(0)
  else:
    print(n)
elif n<=num1:
  print(sum(alist[0:n]))
else:
  cycle=(n-num1+1)//(num2-num1)
  print(sum(alist[0:num1])+cycle*sum(alist[num1:num2+1])+sum(alist[num1:n-cycle*(num2-num1)]))

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,raw_input().split()) 
v=[x] 
t={x:1} 
ok=1
while True: 
    y=(x*x)%m 
    if y==0: 
        print sum(v);ok=0;break
    if y in t: 
        break 
    else: 
        t[y]=1 
        v.append(y) 
        x=y 
g=n%(len(v)) 
ans=0
for i in range(len(v)): 
    if i>g: 
        ans+=((n/len(v))*(v[i]) )
        
    else: 
        ans+=((n/len(v)+1)*v[i]) 
if ok:
    print ans

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
first = [0] * (m+1)

a = [x]
first[x] = 1
for i in range(2,m+10):
    x = pow(x,2,m)
    if(first[x] != 0):
        break
    first[x] = i
    a.append(x)

# print(a)

if(i-1 >= n):
    ans = sum(a[:n])
    print(ans)
    exit()

cyc = a[first[x]-1:]
for j in range(1,len(cyc)):
    cyc[j] += cyc[j-1]

ans = sum(a[:first[x]-1])
# print(ans)
rem = n - first[x] + 1
ans += cyc[-1] * (rem//len(cyc))
# print(ans)
ans += cyc[rem%len(cyc) - 1]
print(ans)

Submission status: Wrong Answer

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 = []

c.append(b)

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) - a[1])
else:
    print(sum(c) - a[1])

Submission status: Wrong Answer

Solution code:
n,x,m= list(map(int, input().strip().split()))
a=[0]*(m)
for i in range(m):
    a[i]=i*i%m
a=list(set(a))
t=0
b=[]
b.append(x)
if n<m+1:
    for i in range(n):
        t+=b[i]
        b.append(b[-1]**2%m)
else:
    for i in range(m+1):
        b.append(b[-1]**2%m)
        if len(b)>len(list(set(b))):
            break
    
    l=len(b)
    for i in range(l-1):
        if b[i]==b[l-1]:
            q=i
    
    b[-1]=0
    s=0
    for i in range(q,l-1):
        s+=b[i]
    for i in range(q):
        t+=b[i]
    t+=s*(n//(l-q))
print(t)

Submission status: Wrong Answer

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

A = X
sum_A = A
A_list = [X]
for i in range(1, N):
    A = A ** 2 % M
    sum_A += A
    if (A in A_list):
        start = A_list.index(A)
        loop = A_list[start:]
        sum_A += sum(loop)*((N-i)//len(loop)) + sum(loop[:(N-i) % len(loop)])
        break
    else:
        A_list.append(A)

    if (A == 0):
        break

print(sum_A)

Submission status: Wrong Answer

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 d==[]:
  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: Wrong Answer

Solution code:
from collections import deque
N,X,M = map(int, input().split())

nodeset = set()
nodeset.add(X)

nodeq = deque()
nodeq.append(X)

is_finish = False
s,e = 0, N
for i in range(N):
    X = (X*X) % M
    if X in nodeset:
        is_finish = True
        
        for p, start in enumerate(nodeq):
            if X == start:
                s = p
                break
        # ループ終了
        break

    nodeq.append(X)
    nodeset.add(X)

nodelist = list(nodeq)
if is_finish:
    loop_size = len(nodelist) - s # 繰り返し部分のサイズ
    loop_cnt = (N - s) //loop_size # 繰り返し回数
    loop_sum = sum(nodelist[s:]) # 繰り返し部分の和
    alpha = (N - s) % loop_size # すべてやったあとの繰り返し部分の余り
    result = sum(nodelist[:s]) + loop_cnt * loop_sum + sum(nodelist[s:s+alpha])
    print(result)
else:
    print(sum(nodelist))

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,raw_input().split()) 
v=[x] 
t={x:1} 
ok=1
while True: 
    y=(x*x)%m 
    if y==0: 
        print sum(v);ok=0;break
    if y in t: 
        break 
    else: 
        t[y]=1 
        v.append(y) 
        x=y 
g=n%(len(v)) 
ans=0
for i in range(len(v)): 
    if i>=g: 
        ans+=((n/len(v))*(v[i]) )
        
    else: 
        ans+=((n/len(v)+1)*v[i]) 
       
if ok:
    print ans

Submission status: Wrong Answer

Solution code:
N, X, M = list(map(int, input().split()))
loop = []
A_set = set()
# find loop
while not X in A_set:
    loop.append(X)
    A_set.add(X)
    X = (X*X)%M

if loop[-1] == 0:
    print(sum(loop))
else:
    ans = 0

    # ループになる前の部分
    loop_L = loop.index(X)
    ans += sum(loop[0:loop_L])
    N -= loop_L
    print(loop_L, ans)

    # ループ部
    loop = loop[loop_L:]
    loop_size = len(loop)
    loop_S = sum(loop)
    ans += loop_S*(N//loop_size)

    # 端数
    ans += sum(loop[:N%loop_size])

    print(ans)

Submission status: Wrong Answer

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

am=[]

d={}

ch=0

for i in range(m):
  y=x%m
  
  if y==0:
    ch+=1
    break
  if y not in d:
    d[y]=0
    
    am.append(y)
    
    x=y*y
    
  else:
    stop=y
    break
    
if ch>0:
  st=0
  ans=0
  while st<=n-1 and st<=len(am)-1:
    ans+=am[st]
    st+=1
    
  print(ans)

else:
  for i in range(len(am)):
    if am[i]==y:
      now=i
      
  new_am=am[now:]
  s_new=sum(new_am)
  l=len(new_am)
  if n<i:
    print(sum(am[:n+1]))
    
  else:
    s=sum(am[:now])
    rest=n-now
    x=rest//l
    y=rest%l
    print(s+x*s_new+sum(new_am[:y]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, x, m = [int(e) for e in input().split()]

s = set()
l = []

a = x % m
total = a
for i in range(1, n):
    a = (a * a) % m
    if a == 0:
        break
    
    if a in s:
        r = n - i
        p = l.index(a)
        
        lo_total = 0
        for j in range(p, len(l)):
            lo_total += l[j]
        total = lo_total * r // (len(l) - p)

        r %= (len(l) - p)        
        for j in range(p, p + r):
            total += l[j]
        break
    
    s.add(a)
    l.append(a)
    total += a

print(total)

Submission status: Wrong Answer

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:
  if m==1:
    print(0)
  else:
    print(n)
elif n<=num1:
  print(sum(alist[0:n]))
else:
  cycle=(n-num1)//(num2-num1+1)
  print(sum(alist[0:num1])+cycle*sum(alist[num1:num2])+sum(alist[num1:n-cycle*(num2-num1+1)]))

Submission status: Wrong Answer

Solution code:
li = list(map(int,input().split()))
n = li[0]
x = li[1]
m = li[2]
y = x
z = x  
for i in range(n):
    if(i==1):
        continue
    else:
        z = (z*z)%m
        y = y+z
        
    
print(y)

Submission status: Wrong Answer

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

dp = [-1]*(10**5+1)
nums = [-1]*(10**5+1)
nums[x] = 1
dp[0] = 0
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[-1])
else:
    roop = nums[bef] - nums[nex] + 1
    roop_value = r[nums[bef]] - r[nums[nex] - 1]
    plus = r[nums[nex]-1]*(n>=nums[nex])
    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())
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 + 1, len(li))) * q
              + sum(li[i] for i in range(s, s + r)))

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
a1 = X
SUM = X
for i in range(N-1):
    SUM += (a1**2) % M
    a1 = (a1**2) % M
    print(a1)
print(SUM)

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
        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:
n,x,m=map(int,raw_input().split()) 
v=[x] 
t={x:1} 
ok=1
while True: 
    y=(x*x)%m 
    if y==0: 
      print sum(v) 
      ok=0;break
    if y in t: 
        break 
    else: 
        t[y]=1 
        v.append(y) 
        x=y 
g=n%(len(v)) 
ans=0
for i in range(len(v)): 
    if i>=g: 
        ans+=(n/len(v))*(v[i]) 
        ans%=m 
    else: 
        ans+=((n/len(v)+1)*v[i]) 
        ans%=m 
if ok:
    print ans

Submission status: Wrong Answer

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 n<=num1:
  print(sum(alist[0:n]))
else:
  cycle=(n-num1)//(num2-num1+1)
  print(sum(alist[0:num1])+cycle*sum(alist[num1:num2])+sum(alist[num1:n-cycle*(num2-num1+1)]))

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
exist = [0] * (m+1)
ans = 0
imamade = []
cnt = 0
for i in range(n):
    if exist[x] == 1:
        ans += x
        break
    else:
        ans += x
        exist[x] = 1
        imamade.append(x)
        x *= x
        x %= m
        cnt += 1
    if i == n-1:
        print(ans)
        exit()
num = imamade.index(x)
n -= num
ans += sum(imamade[num:]) * (n // (cnt-num) -1)
n %= (cnt-num)
for i in range(n-1):
    x *= x
    x %= m
    ans += x
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, X, M = map(int, input().split())
    a = X
    r = a
    i = 1
    S = {X: (a, 0)}
    ns = True
    while i < N:
        an = (a * a) % M
        if an == 0:
            break
        if ns and an in S:
            l = S[a][1] - S[an][1] + 1
            skip = (N - i - 1) // l
            r += (r - S[an][0]) * skip
            i += l * skip
            ns = False
        if i >= N:
            break
        a = an
        r += a
        S[a] = (r, i)
        i += 1

    return r

# print("Yes" if main() else "No")
print(main())

Submission status: Wrong Answer

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

sum = nbDepart
valeur = nbDepart

for k in range(indice-1):

  print(valeur**2, )
  valeur = valeur**2 % diviseur
  
  sum += valeur

print(sum)