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: Runtime Error

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    A = [-1 for i in range(M)]
    A[0] = X

    start = -1
    end = -1

    cnt = [0 for i in range(M)]
    cnt[X] = 0

    for i in range(1,M*2):
        temp = A[i-1] ** 2
        temp %= M
        if cnt[temp] != 0:
            start = cnt[temp]
            end = i - 1
            break
        A[i] = temp
        cnt[temp] = i

    L = end - start + 1

    if start == -1:
        straight = [0 for i in range(N)]
        for i in range(start):
            straight[i] = straight[i-1] + A[i]
        res = straight[-1]
    elif start == 0:
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        res = (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]
    else:
        straight = [0 for i in range(start)]
        for i in range(start):
            straight[i] = straight[i-1] + A[i]
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        if N >= start:
            res = straight[-1]
            N -= start
        else:
            res = straight[N-1]
            N = 0
        res += (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]

    print(res)



main()

Submission status: Runtime Error

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    A = [-1 for i in range(M)]
    A[0] = X

    start = N
    end = N

    cnt = [0 for i in range(M)]
    cnt[X] = 0

    for i in range(1,M*2):
        temp = A[i-1] ** 2
        temp %= M
        if cnt[temp] != 0:
            start = cnt[temp]
            end = i - 1
            break
        A[i] = temp
        cnt[temp] = i

    # print(A)

    # print(start,end)
    # print(A[start],temp)

    L = end - start + 1

    if start != N:
        straight = [0 for i in range(start)]
        for i in range(start):
            straight[i] = straight[i-1] + A[i]
    else:
        straight = [0]

    if start != -1:
        loop = [0 for i in range(L)]

    if start != N:
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]

    # print(straight)
    # print(loop)

    res = 0

    if start != 0:
        if N >= start:
            res += straight[-1]
            N -= start
        else:
            res += straight[N-1]
            N = 0


    if start != N:
        res += (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]

    print(res)



main()

Submission status: Runtime Error

Solution code:
#import sys
#print(sys.maxsize)
N,X,M=map(int,input().split())
table=list(range(M))
for i in range(M):
    table[i]=((table[i]%M)**2)%M
print(table[471])
start=X%M
rireki=list()
rireki.append(start)
ss=0
for j in range(1,N):
    if table[start] in rireki:
        ss=rireki.index(table[start])
        break
    else:
        rireki.append(table[start])
        start=table[start]
nn=len(rireki)
rep=(N-ss)//(nn-ss)
nokori=N-ss-rep*(nn-ss)
loop=rireki[ss:]
#print(nn)
#print(rep)
#print(sum(loop))
#print(ss)
#print(nokori+rep*(nn-ss)+ss)
if 0 in rireki:
    goukei=sum(rireki)
else:
    goukei=rep*sum(loop)+sum(rireki[:ss])+sum(loop[:nokori])
print(goukei)

Submission status: Runtime Error

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

A = [0] * (M + 1)
firstApearAt = {i:0 for i in range(M)}
A[1] =  X
for i in range(2, M + 1):
    A[i] = (A[i - 1] * A[i - 1]) % M
    if firstApearAt[A[i]]:
        r = i
        l = firstApearAt[A[i]]
        break
    firstApearAt[A[i]] = i
S = sum(A[l:r])

ans = 0
if N <= l - 1:
    ans = sum(A[1:N + 1])
else:
    q, p = (N - l + 1) // (r - l), (N - l + 1) % (r - l)
    ans = sum(A[1:l]) + S * q + sum(A[r:r + p])

print(ans)

Submission status: Runtime Error

Solution code:
def resolve():
  N, X, M = map(int, input().split(" "))
  checked = [False] * M
  val = X
  ans = val
  val_list = [val]
  checked[val] = val

  base = M
  for i in range(N-1):
    val*=val
    if val >= base:
      val %= base

    if checked[val] != False:
      loop_start_index = checked[val]+1

      loop_val = sum(val_list[loop_start_index:])
      loop_length = len(val_list[loop_start_index:])
      
      ans += ((N - i - 1) // loop_length) * loop_val
      segment = val_list[loop_start_index:loop_start_index + ((N - i - 1) % loop_length) ]
      ans += sum(segment)
      break
    ans += val
    checked[val] = i
    val_list.append(val)


  print(ans)

if __name__ == "__main__":
  resolve()

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
a=[]
mod_check_list = [False for _ in range(M)]
a.append(x*x%m)
ind=0
s=0
for i in range(m):
    t=a[i]*a[i]%m
    if mod_check_list[t]:
        ind=a.index(t)
        break
    mod_check_list[t] = True
    a.append(t)
s=sum(a[ind:])
l=len(a)-ind
loop_times = (n-1-ind)//l
answer=loop_times*s
for i in range((n-1-ind)%l):
    answer+=a[i+ind]
print(answer+x+sum(a[:ind]))

Submission status: Runtime Error

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

ans = 0
chck = 0
flag = [0]*(10**5 +1)
lst = [X]

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

    if flag[X] == 1:
        break

    flag[X] = 1
    lst.append(X)

preindex = lst.index(X)

preloop = lst[:index]
loop = lst[index:]

loopnum = (N - len(preloop))//len(loop)
loopafternum = (N - len(preloop))%len(loop)

ans = sum(preloop) + sum(loop)*loopnum + sum(loop[:loopafternum])
print(ans)

Submission status: Runtime Error

Solution code:
def main():

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

    ans = X
    tmp = X
    ary = []

    for i in range(1, N):
        tmp = tmp**2 % M
        if ary.count(tmp) == 1:
            ans = ans + tmp
            break
        else:
            ary.append(tmp)
            ans = ans + tmp

    if i < N:
        tmpsum = 0
        tmpcnt = 0
        for j in reversed(ary):
            tmpsum = tmpsum + j
            tmpcnt = tmpcnt + 1
            if j == tmp:
                break

        if N - i > tmpcnt:
            ans = ans + ((N - i) // tmpcnt) * tmpsum
        
        i = i + ((N - i) // tmpcnt) * tmpcnt

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

    print(ans)

main()

Submission status: Runtime Error

Solution code:
def main():

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

    ans = X
    tmp = X
    ary = []

    for i in range(1, N):
        tmp = tmp**2 % M
        if ary.count(tmp) == 1:
            ans = ans + tmp
            break
        else:
            ary.append(tmp)
            ans = ans + tmp

    tmpsum = 0
    tmpcnt = 0
    for j in reversed(ary):
        tmpsum = tmpsum + j
        tmpcnt = tmpcnt + 1
        if j == tmp:
            break

    if N - i > tmpcnt:
        ans = ans + ((N - i) // tmpcnt) * tmpsum
    
    i = i + ((N - i) // tmpcnt) * tmpcnt

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

    print(ans)

main()

Submission status: Runtime Error

Solution code:
def main():

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

    ans = X
    tmp = X
    ary = []

    for i in range(1, N):
        tmp = tmp**2 % M
        if ary.count(tmp) == 1:
            break
        else:
            ary.append(tmp)
            ans = ans + tmp

    tmpsum = 0
    tmpcnt = 0
    for j in reversed(ary):
        tmpsum = tmpsum + j
        tmpcnt = tmpcnt + 1
        if j == tmp:
            break

    if N - i > tmpcnt:
        ans = ans + ((N - i) // tmpcnt) * tmpsum
    
    i = i + ((N - i) // tmpcnt) * tmpcnt

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

    print(ans)

main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 19 22:03:19 2020

@author: liang
"""

N, X, M = map(int,input().split())
mod_set = {X}
mod_lis = [X]
A = [0]*(10**6+1)
A[0] = X
flag = False
#for i in range(1,N):
for i in range(1,min(10**6,N)):
    tmp = A[i-1]**2%M
    if tmp in mod_set:
        flag = True
        break
    A[i] = tmp
    mod_set.add(tmp)
    mod_lis.append(tmp)

if flag:
    j = mod_lis.index(tmp)
else:
    j = i
T = i - j
ans = 0
if T != 0:  
    ans += sum(mod_lis[:j])
    T_sum = sum(mod_lis[j:])
    """
    【切り捨て演算は必ず()をつけて先に計算】
    """
    ans += T_sum * ((N-j)//T)
    #print((N-j)//T, T_sum)
    T_lis = mod_lis[j:i]   
    ans += sum(T_lis[:(N-j)%T])
else:
    ans = sum(mod_lis)
#print(T_lis)
#print((N-j)%T)
#print(T_lis[:10])
print(ans)
#print(T_sum)
#print(sum(T_lis))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 19 22:03:19 2020

@author: liang
"""

N, X, M = map(int,input().split())
mod_set = {X}
mod_lis = [X]
A = [0]*(10**6+1)
A[0] = X
flag = False
#for i in range(1,N):
for i in range(1,min(10**6,N)):
    tmp = A[i-1]**2%M
    if tmp in mod_set:
        flag = True
        break
    A[i] = tmp
    mod_set.add(tmp)
    mod_lis.append(tmp)

if flag:
    j = mod_lis.index(tmp)
else:
    j = i
T = i - j
ans = 0
if T != -1:  
    ans += sum(mod_lis[:j])
    T_sum = sum(mod_lis[j:])
    """
    【切り捨て演算は必ず()をつけて先に計算】
    """
    ans += T_sum * ((N-j)//T)
    #print((N-j)//T, T_sum)
    T_lis = mod_lis[j:i]   
    ans += sum(T_lis[:(N-j)%T])
else:
    ans = sum(mod_lis)
#print(T_lis)
#print((N-j)%T)
#print(T_lis[:10])
print(ans)
#print(T_sum)
#print(sum(T_lis))

Submission status: Runtime Error

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

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: Runtime Error

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
n,x,m = readInts()
lis = []
prv = None
dic = defaultdict(int)
for i in range(m):
    if i == 0:
        A = x%m
        lis.append(A)
        dic[A] = 1
    else:
        A = (A*A)%m
        if dic[A]:
            prv = A
            break
        else:
            dic[A] = 1
        lis.append(A)
cnt = None
for i in range(len(lis)):
    if lis[i] == prv:
        cnt = i
        break
if cnt == None:
    cnt = len(lis)
# front_arr = lis[:cnt]
# print(lis)
# loop_arr = lis[cnt:]
# print(loop_arr)
if x == 0:
    print(0)
    exit()
len_loop_arr = len(loop_arr)
if n < cnt:
    ans = sum(front_arr[:n])
else:
    ans = sum(front_arr)
    sum_loop_arr = sum(loop_arr)
    n -= cnt

    loop = n//len_loop_arr
    rest = n - (loop*len_loop_arr)
    mid = loop * sum_loop_arr
    ans += mid
    ans += sum(loop_arr[:rest])
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 19 22:03:19 2020

@author: liang
"""

N, X, M = map(int,input().split())
mod_set = {X}
mod_lis = [X]
A = [0]*(10**6+1)
A[0] = X
#for i in range(1,N):
for i in range(1,min(10**6,N)):
    tmp = A[i-1]**2%M
    if tmp in mod_set:
        break
    A[i] = tmp
    mod_set.add(tmp)
    mod_lis.append(tmp)

j = mod_lis.index(tmp)
T = i - j
ans = 0
if T != 0:  
    ans += sum(mod_lis[:j])
    T_sum = sum(mod_lis[j:])
    """
    【切り捨て演算は必ず()をつけて先に計算】
    """
    ans += T_sum * ((N-j)//T)
    #print((N-j)//T, T_sum)
    T_lis = mod_lis[j:i]   
    ans += sum(T_lis[:(N-j)%T])
else:
    ans = sum(mod_lis)
#print(T_lis)
#print((N-j)%T)
#print(T_lis[:10])
print(ans)
#print(T_sum)
#print(sum(T_lis))