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:
import numpy as np
N,X,M=map(int,input().split())
A = [X,]
alast=X
flag=False
for i in range(min(N-1,M)):
    P=alast**2%M
    if P in A:
        flag=True
        d = A.index(P)
        C=A[d:]
        alast=P
        break
    else:
        A.append(P)
        alast=P
if alast==0:
    print(sum(C))
elif flag==False:
    print(sum(A))
else:
    suma=sum(C)
    res = (N-d)%len(C)
    print(sum(A[:d])+((N-d)//len(C))*suma + sum(C[:res]))

Submission status: Wrong Answer

Solution code:
""" E
    https://atcoder.jp/contests/abc173/tasks/abc173_e
"""
import sys
import math
from functools import reduce

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(N, X, M):
    A = X
    l = [A]
    i = -1
    for _ in range(1, M):
        A = (A * A) % M if M > 0 else 0
        l.append(A)

    if i == -1:
        return sum(l)
    else:
        s1 = sum(l[:i])
        len_repeat = len(l) - i
        s2 = sum(l[i:])

        return s1 + int((N-i)/len_repeat) * s2 + sum(l[i:(N-i)%len_repeat+i])

if __name__ == "__main__":
    _N, _X, _M = readIntegerSet(3)

    print(main(_N, _X, _M))

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
A = [X]
A_dict = {X}
a = X
s = X
r = 0
r0 = 0
l = 0
amari = 0

for i in range(M+1):
  a = a ** 2 % M
  if a in A_dict:
    r0 = A.index(a)
    l = len(A[r0:])
    r = (N - i - 1) // l
    amari = (N - i - 1) % l
    s = sum(A[:r0]) + sum(A[r0:])*r + sum(A[r0:r0+amari])
    break
  A.append(a)
  A_dict.add(a)

print(s)

Submission status: Wrong Answer

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

dic = {}
tmp = []

a = x
sum_a = x
for i in range(n - 1):
    if a in dic:
        idx0 = dic[a] - 1
        idx1 = i - 1
        period = idx1 - idx0
        times = (n - 1 - idx0) // period
        res = (n - 1 - idx0) % period
        before = tmp[idx0]
        ans = tmp[idx0 + res] + (tmp[idx1] - tmp[idx0]) * times
        print(ans)
        break
    else:
        tmp.append(sum_a)
        dic[a] = i
        a = a ** 2 % m
        sum_a += a
else:
    print(sum_a)

Submission status: Wrong Answer

Solution code:
""" E
    https://atcoder.jp/contests/abc173/tasks/abc173_e
"""
import sys
import math
from functools import reduce

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(N, X, M):
    A = X
    l = [A]
    i = -1
    for _ in range(1, M):
        A = A # (A * A) % M if M > 0 else 0
        if A in l:
            i = l.index(A)
            break
        else:
            l.append(A)

    if i == -1:
        return sum(l)
    else:
        s1 = sum(l[:i])
        len_repeat = len(l) - i
        s2 = sum(l[i:])

        return s1 + int((N-i)/len_repeat) * s2 + sum(l[i:(N-i)%len_repeat+i])

if __name__ == "__main__":
    _N, _X, _M = readIntegerSet(3)

    print(main(_N, _X, _M))

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
mod = m
amari = [-1]*m
a = x
cnt = 1
l = 0
r = 0
while 1:
    # print(a)
    if cnt == n:
        break
    
    if amari[a] != -1:
        l = amari[a]
        r = cnt
        # print(a,amari[a])
        break
    else:
        amari[a] = cnt
    cnt += 1
    a = ((a % m)**2) % m
    # if cnt > m:
    #     print("error")
    #     exit()
ans = 0
if cnt == n:
    l = 0
    r = n
# print(l,r)
a = x
temp = 0

for i in range(l-1):
    ans += a
    a = (a**2) % mod
# print(ans)


for i in range(r-l):
    temp += a
    a = (a**2) % mod
ans += temp * ((n-l+1)//(r-l))
# print(ans,a,temp,temp * (n-l)//(r-l),(n-l)//(r-l))


if r != n:
    for i in range((n-l+1)%(r-l)):
        ans += a
        a = (a**2) % mod
        # print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
""" E
    https://atcoder.jp/contests/abc173/tasks/abc173_e
"""
import sys
import math
from functools import reduce

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(N, X, M):
    A = X
    l = [A]
    i = -1
    for _ in range(1, M):
        A = (A * A) % M if M > 0 else 0
        if A in l:
            i = l.index(A)
            break
        else:
            l.append(A)

    if i == -1:
        return sum(l)
    else:
        s1 = sum(l[:i])
        len_repeat = len(l) - i
        s2 = sum(l[i:])

        # return s1 + int((N-i)/len_repeat) * s2 + sum(l[i:(N-i)%len_repeat+i])

if __name__ == "__main__":
    _N, _X, _M = readIntegerSet(3)

    print(main(_N, _X, _M))

Submission status: Wrong Answer

Solution code:
import math

n, x, m = map(int, input().split())
ans = x % m
loop_lis = []
loop_num = 0
before_cnt = 1
while pow(x, 2) <= m:
    if before_cnt == n:
        print(ans)
        exit()
    tmp = pow(x, 2)
    before_cnt += 1
    tmp %= m
    ans += tmp
    x = tmp

loop_lis = [pow(x, 2) % m]
x = pow(x, 2) % m

for i in range(1, m):
    if before_cnt + i == n:
        ans += loop_lis[-1]
        break
    tmp = pow(x, 2) % int(m)
    if loop_lis[0] == tmp:
        remain = (n - before_cnt) % len(loop_lis)
        loop_num = math.floor((n - before_cnt) / len(loop_lis))
        if remain == 0:
            ans += loop_num * loop_lis[-1]
        else:
            ans += loop_num * loop_lis[-1] + loop_lis[remain - 1]
        break
    loop_lis.append(tmp + loop_lis[-1])
    x = tmp
print(ans)

Submission status: Wrong Answer

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

cnt = 0
flag = True
ruiseki = [x]
a = x
al = {}
al[x] = 0
loop_s = 0
loop_e = 0

for i in range(n - 1):
    na = (a ** 2) % m
    if na in al.keys():
        loop_s = al[na]
        loop_e = al[a]
        break
    else:
        al[na] = i + 1
        ruiseki.append(ruiseki[cnt] + na)
        cnt += 1
        a = na

if loop_e != 0:
    ans = ruiseki[loop_s - 1] + (ruiseki[loop_e] - ruiseki[loop_s - 1]) * (n // (loop_e - loop_s + 1))
    p = max(0, n - (loop_s - 1 + (n // (loop_e - loop_s + 1)) * (loop_e - loop_s + 1)))
    if p != 0:
        ans += ruiseki[p] - ruiseki[loop_s - 1]
else:
    ans = ruiseki[-1]

print(ans)

Submission status: Wrong Answer

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

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

        # ans = sum(prev_list[:index])
        # ans += sum(prev_list[index:i]) * count
        ans += (ans - ans_hist[index - 1]) * (count - 1)

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

Submission status: Wrong Answer

Solution code:
n, x, m = (int(x) for x in input().split())
dic = {}
count = 1
dic[x]=0
ans = [x]
bool = True
while (count < n):
    x = pow(x, 2, m)
    if x not in dic:
        dic[x] = count
        ans.append(ans[count-1] + x)
    else:
        aida = ans[dic[x]:count]
        saisyuutekinakotae = ans[dic[x]-1]
        for i in range(len(aida)):
            aida[i]-=ans[dic[x]-1]
        nokottakosuu = n-dic[x]
        syuukisuu = nokottakosuu//len(aida)
        hasuu = nokottakosuu%len(aida)
        saisyuutekinakotae += syuukisuu*aida[-1]
        saisyuutekinakotae += aida[hasuu-1]
        bool = False
        print(saisyuutekinakotae)
        count = pow(10, 13)
    count+=1
if bool:
    print(ans[n-1])

Submission status: Wrong Answer

Solution code:
N ,X, M = map(int,input().split())
L = [X]
A = X
x = 0
for i in range(N):
  A = A**2 % M
  if A in L:
    x = L.index(A)
    break
  else:
    L.append(A)

##if 0 in L:
##  if N <= len(L):
#    print(sum(L[:N]))
#  else:
#    print(sum(L))
#else:b

ans = sum(L[:x]) + ((N) // (len(L)-x))* sum(L[x:]) + sum(L[x:((N)%((len(L)-x)))])
print(ans)

Submission status: Wrong Answer

Solution code:
N ,X, M = map(int,input().split())
L = [X]
A = X
x = 0
for i in range(N):
  A = A**2 % M
  if A in L:
    x = L.index(A)
    break
  else:
    L.append(A)
print(L)
##if 0 in L:
##  if N <= len(L):
#    print(sum(L[:N]))
#  else:
#    print(sum(L))
#else:b

ans = sum(L[:x]) + ((N) // (len(L)-x))* sum(L[x:]) + sum(L[x:((N)%((len(L)-x)))])
print(ans)

Submission status: Wrong Answer

Solution code:
# Date [ 2020-09-19 21:46:14 ]
# Problem [ e.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, x, m = read_ints()
    query = []
    s = set([])
    while x not in s:
        s.add(x)
        query.append(x)
        x = x * x % m
    
    frm = query.index(x)
    length = len(query) - frm
    total = sum(query[frm:])
    
    ans = sum(query[:frm]) + total * (n - frm) // length + sum(query[frm:frm + (n - frm) % length])
    print(ans)

if __name__ == '__main__':
    Main()

Submission status: Wrong Answer

Solution code:
n,x, m = map(int, input().split())
mod = [None for _ in range(m)]
count = x
loop = []
rem = []
for i in range(1, n):
    value = x * x % m
    rem.append(value)
    x = x * x % m
    if mod[value] != None:
        # print(mod)
        s_index = mod[value]
        loop = rem[s_index :]
        num = (n - s_index) // len(loop)
        amari = (n - s_index) % len(loop)
        if amari == 0:
            print(count + sum(loop) * num) 
        else:
            print(count + sum(loop) * num + sum(loop[:amari - 1])) 
        exit()
    else:
        mod[value] = i
        count += value
print(count)

Submission status: Wrong Answer

Solution code:
import math
n,x,m=map(int, input().split())
a = x
ans = a
lp=0
l=[a]
flg=[0]*m

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

if lp != 0:
    l2 = l[lp:]
    tmp = sum(l2)
    b=math.floor((n-len(l))/len(l2))
    c=(n-len(l))%len(l2)
    if c==0:
        ans+=b*tmp
    else:
        ans+=b*tmp+sum(l2[:c])-l2[0]

print(ans)

Submission status: Wrong Answer

Solution code:
""" E
    https://atcoder.jp/contests/abc173/tasks/abc173_e
"""
import sys
import math
from functools import reduce

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(N, X, M):
    A = X
    l = [A]
    i = -1
    for _ in range(1, N):
        A = (A * A) % M if M > 0 else 0
        if A in l: 
            i = l.index(A)
        else:
            l.append(A)

    if i == -1:
        return sum(l)
    else:
        s1 = sum(l[:i])
        len_repeat = len(l) - i
        s2 = sum(l[i:])

        return s1 + int((N-i)/len_repeat) * s2 + sum(l[i:(N-i)%len_repeat+i])

if __name__ == "__main__":
    _N, _X, _M = readIntegerSet(3)

    print(main(_N, _X, _M))

Submission status: Wrong Answer

Solution code:
N ,X, M = map(int,input().split())
L = [X]
A = X
x = 0
for i in range(N-1):
  A = A**2 % M
  if A in L:
    x = L.index(A)
    break
  else:
    L.append(A)

##if 0 in L:
##  if N <= len(L):
#    print(sum(L[:N]))
#  else:
#    print(sum(L))
#else:

ans = sum(L[:x]) + ((N) // (len(L)-x))* sum(L[x:]) + sum(L[x:((N)%((len(L)-x)))])
print(ans)

Submission status: Wrong Answer

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

for i in range(n):
    if i == 0:
        pass
    else:
        r = (r * r) % m
    
    if r == 0:
        break
    
    if r in prev_set:
        index = prev_list.index(r)
        period = i - index
        count = (n - index) // period
        rest = (n - index) % period
        ans += (ans - ans_hist[index - 1]) * (count - 1)
        ans += (ans_hist[index + rest - 1] - ans_hist[index - 1])
        break
    else:
        ans += r
        prev_set.add(r)
        prev_list.append(r)
        ans_hist.append(ans)
print(ans)

Submission status: Wrong Answer

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

for i in range(n):
    if i == 0:
        pass
    else:
        r = (r * r) % m
    
    if r == 0:
        break
    
    if r in prev_set:
        index = prev_list.index(r)
        period = i - index
        count = (n - index) / period
        rest = (n - index) % period
        ans += (ans - ans_hist[index - 1]) * (count - 1)
        ans += (ans_hist[index + rest - 1] - ans_hist[index - 1])
        break
    else:
        ans += r
        prev_set.add(r)
        prev_list.append(r)
        ans_hist.append(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,x,m=map(int,input().split())
s=[x]
g=set()
cnt=0
l=-1
g.add(x)
b=x
for i in range(1,n):
    nt=pow(b,2,m)
    b=nt
    print(b)
    if nt not in g:
        s.append(nt)
        g.add(nt)
    else:
        cnt=i
        l=nt
        break
if l==0:
    #s=list(s)
    ans=sum(s)
elif l==1:
    #s=list(s)
    ans=n-cnt+sum(s)
else:
    if l!=-1:
      idx=s.index(l)
      c=len(s)-idx
      r=(n-cnt)%c
      ans=((n-cnt)//c)*sum(s[idx:])+sum(s[idx:idx+r])+sum(s)
    else:
      ans=sum(s)
print(ans)

Submission status: Wrong Answer

Solution code:
N ,X, M = map(int,input().split())
L = [X]
A = X
x = 0
for i in range(N-1):
  A = A**2 % M
  if A in L:
    x = L.index(A)
    break
  else:
    L.append(A)
if 0 in L:
  if N <= len(L):
    print(sum(L[:N]))
  else:
    print(sum(L))
else:
  ans = sum(L[:x]) + ((N) // (len(L)-x))* sum(L[x:]) + sum(L[x:((N)%((len(L)-x)))])
  print(ans)

Submission status: Wrong Answer

Solution code:


def main():
    n, x, m = map(int, input().split())
    mflg = [-1] * m
    if x < m:
        mflg[x] = 0
    ltot = [x]

    tot = x
    a = x
    for i in range(1, n):
        a = a ** 2 % m
        
        if mflg[a] >= 0:
            b = mflg[a]
            z = (n - i - 1) // (i - b) - 1
            y = (n - i - 1) % (i - b)
            tot += (ltot[b - 1 + y] - ltot[b - 1]) + (ltot[-1] - ltot[b - 1]) * z
            break

        mflg[a] = i
        tot += a
        ltot.append(tot)

    print(tot)


main()

Submission status: Wrong Answer

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

for i in range(1, m + 1):
    x = pow(x, 2, m)
    if loop_list[x] != 1:
        loop_list[x] = 1
        order_list.append(x)
    else:
        break

index = order_list.index(x)
time = (n - index) // (len(order_list) - index)
mod = (n - index) % (len(order_list) - index)

ans += sum(order_list[:index - 1])
ans += sum(order_list[index:]) * time
ans += sum(order_list[index:index + mod - 1])

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,X,M=map(int,input().split())
A = [X,]
alast=X
flag=False
for i in range(min(N-1,M)):
    P=alast**2%M
    if P in A:
        flag=True
        d = int(np.arange(len(A))[np.array(A)==P])
        C=A[d:]
        alast=P
        break
    else:
        A.append(P)
        alast=P
if alast==0:
    print(sum(C))
elif flag==False:
    print(sum(A))
else:
    suma=sum(C)
    res = (N-d)%len(C)
    print(sum(A[:d])+((N-d)//len(C))*suma + sum(C[:res]))

Submission status: Wrong Answer

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

a = [x]
b = [x]
rabbit = x
turtle = x
flag = False

start = 0
end = 1

while True:
  rabbit = (rabbit ** 2) % m
  rabbit = (rabbit ** 2) % m
  turtle = (turtle ** 2) % m
  a.append(turtle)
  b.append(b[-1] + turtle)
  
  if rabbit == turtle:
    break

if len(a) >= n:
  print(b[n - 1])
elif a[-1] == 0:
  print(b[-1])
else:
  rabbit = x
  while rabbit != turtle:
    rabbit = (rabbit ** 2) % m
    turtle = (turtle ** 2) % m
    start += 1
    a.append(turtle)
    b.append(b[-1] + turtle)

  turtle = (turtle ** 2) % m
  end = start + 1
  a.append(turtle)
  b.append(b[-1] + turtle)
  while rabbit != turtle:
    turtle = (turtle ** 2) % m
    end += 1
    a.append(turtle)
    b.append(b[-1] + turtle)

  if len(a) >= n:
    print(b[n - 1])
  elif a[-1] == 0:
    print(b[-1])
  else:
    ans = b[start - 1]
    ans += (b[end - 1] - b[start - 1]) * ((n - start) // (end - start))
    if (n - start) % (end - start) != 0:
      ans += b[((n - start) % (end - start)) + start - 1] - b[start - 1]
    print(ans)

Submission status: Wrong Answer

Solution code:


def main():
    n, x, m = map(int, input().split())
    mflg = [-1] * (m)
    if x < m:
        mflg[x] = 0
    ltot = [x]

    tot = x
    a = x
    for i in range(1, n):
        a = a ** 2 % m
        if mflg[a] >= 0:
            b = mflg[a]
            z = (n - i) // (i - b) - 1
            y = (n - i) % (i - b)
            tot += (ltot[b - 1 + y] - ltot[b - 1]) + (ltot[-1] - ltot[b - 1]) * z
            break

        mflg[a] = i
        tot += a
        ltot.append(tot)

    print(tot)


main()

Submission status: Wrong Answer

Solution code:


def main():
    n, x, m = map(int, input().split())
    mflg = [-1] * (m)
    if x < m:
        mflg[x] = 0
    ltot = [x]

    tot = x
    a = x
    for i in range(1, n):
        a = a ** 2 % m
        if mflg[a] >= 0:
            b = mflg[a]
            z = (n - i) // (i - b) - 1
            y = (n - i) % (i - b)
            tot += (ltot[b - 1 + y] - ltot[b - 1]) + (ltot[-1] - ltot[b - 1]) * z
            break

        mflg[a-1] = i
        tot += a
        ltot.append(tot)

    print(tot)


main()

Submission status: Wrong Answer

Solution code:
import math

n, x, m = map(int, input().split())
ans = x % m
loop_lis = []
loop_num = 0
before_cnt = 1
while True:
    if before_cnt == n:
        print(ans)
        exit()
    tmp = pow(x, 2)
    if tmp >= m:
        loop_lis = [tmp % m]
        x = tmp
        break
    before_cnt += 1
    tmp %= m
    ans += tmp
    x = tmp
for i in range(1, m):
    if before_cnt + i == n:
        ans += loop_lis[-1]
        break
    tmp = pow(x, 2) % int(m)
    if loop_lis[0] == tmp:
        remain = (n - before_cnt) % len(loop_lis)
        loop_num = math.floor((n - before_cnt) / len(loop_lis))
        if remain == 0:
            ans += loop_num * loop_lis[-1]
        else:
            ans += loop_num * loop_lis[-1] + loop_lis[remain - 1]
        break
    loop_lis.append(tmp + loop_lis[-1])
    x = tmp
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,X,M=map(int,input().split())
A = [X,]
alast=X
flag=False
for i in range(min(N,M)):
    P=alast**2%M
    if P in A:
        flag=True
        d = int(np.arange(len(A))[np.array(A)==P])
        C=A[d:]
        alast=P
        break
    else:
        A.append(P)
        alast=P
if alast==0:
    print(sum(C))
elif flag==False:
    print(sum(A))
else:
    suma=sum(C)
    res = (N-d)%len(C)
    print(sum(A[:d])+((N-d)//len(C))*suma + sum(C[:res]))

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
mod = m
amari = [-1]*m
a = x
cnt = 1
l = 0
r = 0
while 1:
    # print(a)
    if cnt == n:
        break
    
    if amari[a] != -1:
        l = amari[a]
        r = cnt
        # print(a,amari[a])
        break
    else:
        amari[a] = cnt
    cnt += 1
    a = ((a % m)**2) % m
    # if cnt > m:
    #     print("error")
    #     exit()
ans = 0
if cnt == n:
    l = 0
    r = n
# print(l,r)
a = x
temp = 0
for i in range(l-1):
    ans += a
    a = (a**2) % mod
# print(ans)
for i in range(r-l):
    temp += a
    a = (a**2) % mod
ans += temp * ((n-l)//(r-l))
# print(ans,a,temp,temp * (n-l)//(r-l),(n-l)//(r-l))
if r != n:
    for i in range((n-l+1)%(r-l)):
        ans += a
        a = (a**2) % mod
        # print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,x,m=map(int,input().split())
s=[x]
g=set()
cnt=0
l=-1
g.add(x)
b=x
for i in range(1,n):
    nt=pow(b,2,m)
    b=nt
    if nt not in g:
        s.append(nt)
        g.add(nt)
    else:
        cnt=i
        l=nt
        break
if l==0:
    #s=list(s)
    ans=sum(s)
elif l==1:
    #s=list(s)
    ans=n-cnt+1+sum(s)
else:
    if l!=-1:
      idx=s.index(l)
      c=len(s)-idx
      r=(n-cnt)%c
      ans=((n-cnt)//c)*sum(s[idx:])+sum(s[idx:idx+r])+sum(s)
    else:
      ans=sum(s)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
import bisect #二部探索
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化
INF = 10**9 + 7
mod = 10**9 + 7
def f(x, m):
    return pow(x, 2) % m

def main():
    n, x, m = list(map(int,input().split()))
    a = x
    #print(a)
    a_list = [x]
    roop_flag = False
    for i in range(n):
        a = f(a, m)
        #print(a)

        if a == 0:
            break
        if not a in a_list:
            a_list.append(a)
        else:
            roop_flag = True
            break #繰り返しの始まりはaに入ったまま
    if not roop_flag:
        ans = sum(a_list)
        print(ans)
    else:
        #繰り返しが始まるまで(a_list.index(a) - 1)個
        roop_f = int(a_list.index(a))
        #print(roop_f)
        ans = sum(a_list[: roop_f])
        #print(ans)
        n -= roop_f - 1 # 残りの数
        #ループする回数
        n_roop = n // (len(a_list) - roop_f)
        ans += sum(a_list[roop_f :]) * n_roop
        n %= n_roop #残りの数
        #最後
        ans += sum(a_list[roop_f: roop_f + n - 1])
        print(ans)

    return 0

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,x,m=map(int,input().split())
s=[x]
g=set()
cnt=0
l=-1
g.add(x)
b=x
for i in range(1,n):
    nt=pow(b,2,m)
    b=nt
    if nt not in g:
        s.append(nt)
        g.add(nt)
    else:
        cnt=i
        l=nt
        break
if l==0:
    #s=list(s)
    ans=sum(s)
elif l==1:
    #s=list(s)
    ans=n-cnt+1+sum(s)
else:
    if l!=-1:
      idx=s.index(l)
      c=len(s)-idx
      r=(n-cnt)%c
      print(idx,r)
      ans=((n-cnt)//c)*sum(s[idx:])+sum(s[idx:idx+r])+sum(s)
    else:
      ans=sum(s)
print(ans)

Submission status: Wrong Answer

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

S = []
pre_Ai = X
A = pre_Ai
break_num = 0

for i in range(N-1):
  Ai= (pre_Ai**2)%M
  if pre_Ai**2>M or break_num!=0: 
    if Ai not in S:
      S.append(Ai)
      break_num = 1
    else:
      break_num = i
      break
  A += Ai
  pre_Ai = Ai 
  if Ai==0:
    break

if break_num!=0:
  A += int((N-break_num-1)/len(S))*sum(S)
  for i in range((N-break_num-1)%len(S)):
    A += S[i]

print(A)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
import bisect #二部探索
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化
INF = 10**9 + 7
mod = 10**9 + 7
def f(x, m):
    return pow(x, 2) % m

def main():
    n, x, m = list(map(int,input().split()))
    a = x
    #print(a)
    a_list = [x]
    roop_flag = False
    for i in range(n):
        a = f(a, m)
        #print(a)

        if a == 0:
            break
        if not a in a_list:
            a_list.append(a)
        else:
            roop_flag = True
            break #繰り返しの始まりはaに入ったまま
    if not roop_flag:
        ans = sum(a_list)
        #print(ans)
    else:
        #繰り返しが始まるまで(a_list.index(a) - 1)個
        roop_f = int(a_list.index(a))
        #print(roop_f)
        ans = sum(a_list[: roop_f])
        #print(ans)
        n -= roop_f - 1 # 残りの数
        #ループする回数
        n_roop = n // (len(a_list) - roop_f)
        ans += sum(a_list[roop_f :]) * n_roop
        n %= n_roop #残りの数
        #最後
        ans += sum(a_list[roop_f: roop_f + n - 1])
        print(ans)

    return 0

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
mod = m
amari = [-1]*m
a = x
cnt = 1
l = 0
r = 0
while 1:
    # print(a)
    if cnt == n:
        break
    
    if amari[a] != -1:
        l = amari[a]
        r = cnt
        # print(a,amari[a])
        break
    else:
        amari[a] = cnt
    cnt += 1
    a = ((a % m)**2) % m
    # if cnt > m:
    #     print("error")
    #     exit()
ans = 0
if cnt == n:
    l = 0
    r = n
# print(l,r)
a = x
temp = 0
for i in range(l-1):
    ans += a
    a = (a**2) % mod
# print(ans)
for i in range(r-l):
    temp += a
    a = (a**2) % mod
ans += temp * ((n-l)//(r-l))
# print(ans,a,temp,temp * (n-l)//(r-l),(n-l)//(r-l))
for i in range((n-l+1)%(r-l)):
    ans += a
    a = (a**2) % mod
    # print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
"""
何回足されるかで考えればよい。
真っ二つに切っていく。

各項は必ずM未満。
M項以内に必ずループが現れる。
"""
N,X,M = map(int,input().split())
memo1 = set()
memo2 = []
ans = 0
a = X
flag = True
rest = N
while rest > 0:
    if a in memo1 and flag:
        flag = False
        for i in range(len(memo2)):
            if memo2[i] == a:
                loopStart = i
        setSum = 0
        for i in range(loopStart,len(memo2)):
            setSum += memo2[i]**2 % M
        loopStep = len(memo2)-loopStart
        loopCount = rest // loopStep
        ans += loopCount*setSum
        rest -= loopCount*loopStep
    
    memo1.add(a)
    memo2.append(a)
    ans += a
    a = a**2%M
    rest -= 1

print(ans)

Submission status: Wrong Answer

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

count = 0

# table2jou = []
# for mi in range(m + 1):
#     table2jou.append(pow(mi, 2))

tablef = []
for mi in range(m + 1):
    # tablef.append(table2jou[mi] % m)
    tablef.append(pow(mi, 2, m))


count = x
pre_an = x
his = [x]
for ni in range(2, n + 1):
    an = tablef[pre_an]
    if an in his:
        leftnum = n - ni + 1
        start = his.index(an)
        end = leftnum % (len(his) - start) + start
        loopnum = leftnum // (len(his) - start)
        count = count + sum(his[start: end + 1])
        count = count + sum(his[start:]) * loopnum
        break
    his.append(an)
    count = count + an
    pre_an = an

print(count)

Submission status: Wrong Answer

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

res = X
remainder_list = set([X % M])
remainder_loop = []

a_part = []

flg = False

a = X

for i in range(N - 1):
    a = a ** 2 % M
    res += a
    res_trig = a
    if a in remainder_list:
        loop_length = 0
        loop_sum = [0]
        while True:
            a = a ** 2 % M
            loop_sum.append(loop_sum[-1] + a)
            loop_length += 1
            if a == res_trig:
                break
        res += (N - i - 1) // loop_length * loop_sum[-1]
        res += loop_sum[(N - i - 1) % loop_length - 1]
        break
    else:
        remainder_list.add(a)

print(res)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int,input().split())
lst = [0 for i in range(m)]
lst2 = [x]
i = 2
lst[x] = 1
c = 0
while True:
    if (i > n):
        break
    x = x**2%m
    if (lst[x] == 0):
        lst[x] = i
        lst2.append(lst2[i - 2] + x)
        i = i + 1
    else:
        lst2.append(lst2[i - 2] + x)
        c = 1
        break
if (c == 1):
    a = i - lst[x]
    b = lst2[i - 1] - lst2[i - 1 - a]
    i = i - 1
    c = (n - i)//a
    d = (n - i)%a
    ans = lst2[i - 1] + b*c + lst2[i - 1 - a + d] - lst2[i - 1 - a]
    print(ans)

else:
    print(lst2[n - 1])

Submission status: Wrong Answer

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

lst_sum = [0,x]
loop = [0]*(10**5)
loop[x] = 1
s = 1
for i in range(2,n+1):
  y = ((lst_sum[-1] - lst_sum[-2])**2)%m
                          
  if loop[y] != 0:
    l = i-loop[y]
    d = (n-loop[y]+1) // l
    q = (n-loop[y]+1) % l
    sum_loop = lst_sum[-1]-lst_sum[loop[y]-1]
    sum_first = lst_sum[loop[y]-1]
    if q == 0:
      sum_rest = 0
    else:
      sum_rest = lst_sum[loop[y] + q-1] - lst_sum[loop[y]-1]
    print(sum_first+d*sum_loop+sum_rest)
    sys.exit()      
  else:
    s += 1
    loop[y] = s
    lst_sum.append(lst_sum[-1] + y)