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:
#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
front_arr = lis[:cnt]

loop_arr = lis[cnt:]
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:
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 = []
        while True:
            a = a ** 2 % M
            if len(loop_sum) == 0:
                loop_sum.append(a)
            else:
                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 - 2]
        break
    else:
        remainder_list.add(a)

print(res)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
table = [0]*(M+1)

pre = X
table[pre] = 1
seq = [pre]
cnt = 0
while True:
    cnt += 1
    A = pre**2%M
    if not table[A]:
        seq.append(A)
        table[A] = cnt
        pre = A
    else:
        fir = table[A]
        sec = cnt
        break
    
ans = 0
for i in range(fir + (N-fir)%(sec-fir)):
    ans += seq[i]
mul = (N-fir)//(sec-fir)
for i in range(fir, sec):
    ans += seq[i]*mul

print(ans)

Submission status: Runtime Error

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

a = [x] + [0]*(n-1)
sum = 0

for i in range (0,n-1):
    a[i+1] = (a[i]**2) % m
    sum += a[i]
    if a[i+1] == 0:
        break
else:
    sum += a[n-1]

print(sum)

Submission status: Runtime Error

Solution code:


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

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

    print(tot)


main()

Submission status: Runtime Error

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

lst, num, frag = set(), [], False
for i in range(1, n + 1):
    lst.add(x), num.append(x)
    x = x ** 2 % m
    if x in lst:
        flag = True
        break

ans = sum(num)
if flag:
    cnt, idx = i, num.index(x)
    div, mod = divmod(n - cnt, len(num) - idx)
    ans += sum(num[idx:idx + mod])
    ans += sum(num[idx:]) * div
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N, X, M = map(int, input().split())

mod_check_list = [False for _ in range(M)]
mod_list = [(X ** 2) % M]
counter = 1
mod_sum = (X ** 2) % M
last_mod = 0
for i in range(M):
    now_mod = (mod_list[-1] ** 2) % M
    if mod_check_list[now_mod]:
        last_mod = now_mod
        break
    mod_check_list[now_mod] = True
    mod_list.append(now_mod)
    counter += 1
    mod_sum += now_mod

loop_start_idx = 0
for i in range(counter):
    if last_mod == mod_list[i]:
        loop_start_idx = i
        break

loop_list = mod_list[loop_start_idx:]
loop_num = counter - loop_start_idx
ans = 0
if mod_list[-1] == 0:
    ans = X + sum(mod_list[:min(counter, N - 1)])
else:
    if (N - 1) <= counter:
        ans = X + sum(mod_list[:counter])
        print(aa)
    else:
        ans += X + mod_sum
        N -= (counter + 1)
        ans += sum(loop_list) * (N // loop_num) + sum(loop_list[:N % loop_num])
print(ans)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
table = [0]*M

pre = X%M
table[pre] = 1
seq = [pre]
cnt = 0
while True:
    cnt += 1
    A = pre**2%M
    if not table[A]:
        seq.append(A)
        table[A] = cnt
        pre = A
    else:
        fir = table[A]
        sec = cnt
        break
    
ans = 0
for i in range(fir + (N-fir)%(sec-fir)):
    ans += seq[i]
mul = (N-fir)//(sec-fir)
for i in range(fir, sec):
    ans += seq[i]*mul

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__len = _len
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])
        # ep(self.__tree[self.__size:])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

    def max_right(self, l, f):
        # https://atcoder.jp/contests/practice2/submissions/16636885
        assert 0 <= l <= self.__len
        if l == self.__len:
            return self.__len

        l += self.__size
        sm = self.__ie
        while True:
            while l % 2 == 0:
                l >>= 1
            if not f(self.__op(sm, self.__tree[l])):
                while l < self.__size:
                    l = 2*l
                    if f(self.__op(sm, self.__tree[l])):
                        sm = self.__op(sm, self.__tree[l])
                        l += 1
                return l - self.__size
            sm = self.__op(sm, self.__tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self.__len

    def min_left(self, r, f):
        assert 0 <= r <= self.__len
        if r == 0:
            return 0

        r += self.__size
        sm = self.__ie
        while True:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not f(self.__op(sm, self.__tree[r])):
                while r < self.__size:
                    r = 2*r + 1
                    if f(self.__op(sm, self.__tree[r])):
                        sm = self.__op(sm, self.__tree[r])
                        r -= 1
                return r + 1 - self.__size
            sm = self.__op(sm, self.__tree[r])

            if (r & -r) == r:
                break

        return 0

    def __getitem__(self, key):
        return self.__tree[key + self.__size]



@mt
def slv(N, K, LR):
    M = 998244353
    memo = SegmentTree([0] * (N+1), add, 0)
    memo.update(1, 1)
    for i in range(2, N+1):
        v = 0
        for l, r in LR:
            v += memo.query(max(0, i-r), max(0, i-l+1))
            v %= M
        memo.update(i, v)

    return memo[N]


def main():
    N, K = read_int_n()
    LR = [read_int_n() for _ in range(K)]
    print(slv(N, K, LR))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
table = [0]*M

table[X] = 1
pre = X
seq = [X]
cnt = 0
while True:
    cnt += 1
    A = pre**2%M
    if not table[A]:
        seq.append(A)
        table[A] = cnt
        pre = A
    else:
        fir = table[A]
        sec = cnt
        break
    
ans = 0
for i in range(fir + (N-fir)%(sec-fir)):
    ans += seq[i]
mul = (N-fir)//(sec-fir)
for i in range(fir, sec):
    ans += seq[i]*mul

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N, X, M = map(int, input().split())

mod_check_list = [False for _ in range(M)]
mod_list = [(X ** 2) % M]
counter = 1
mod_sum = (X ** 2) % M
last_mod = 0
for i in range(M):
    now_mod = (mod_list[-1] ** 2) % M
    if mod_check_list[now_mod]:
        last_mod = now_mod
        break
    mod_check_list[now_mod] = True
    mod_list.append(now_mod)
    counter += 1
    mod_sum += now_mod

loop_start_idx = 0
for i in range(counter):
    if last_mod == mod_list[i]:
        loop_start_idx = i
        break

loop_list = mod_list[loop_start_idx:]
loop_num = counter - loop_start_idx
ans = 0
if mod_list[-1] == 0:
    ans = X + mod_list[:min(counter, N - 1)]
else:
    if (N - 1) <= counter:
        ans = X + sum(mod_list[:counter])
    else:
        ans += X + mod_sum
        N -= (counter + 1)
        ans += sum(loop_list) * (N // loop_num) + sum(loop_list[:N % loop_num])
print(ans)

Submission status: Runtime Error

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

a = [x] + [0]*(n-1)
sum = 0

for i in range (0,n-1):
    a[i+1] = (a[i]**2) % m
    sum += a[i]
else:
    sum += a[n-1]

print(sum)

Submission status: Runtime Error

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

lst, num, frag = set(), [], 0
for i in range(1, n + 1):
    lst.add(x), num.append(x)
    x = x ** 2 % m
    if x in lst:
        flag = 1
        break

ans = sum(num)
if flag == 1:
    cnt, idx = i, num.index(x)
    div, mod = divmod(n - cnt, len(num) - idx)
    ans = sum(num[idx:idx + mod])
    ans += sum(num[idx:]) * div
print(ans)

Submission status: Runtime Error

Solution code:

from __future__ import division, print_function
# import threading
# threading.stack_size(2**27)
# import sys
# sys.setrecursionlimit(10**7)
import sys
from sys import stdin, stdout
import bisect            #c++ upperbound
import math
import heapq
##import numpy as np
##i_m=9223372036854775807
def modinv(n,p):
    return pow(n,p-2,p)
def cin():
    return map(int,sin().split())
def ain():                           #takes array as input
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
def msb(n):         #log2 for n <= 10**10
    n|=n>>1
    n|=n>>2
    n|=n>>4
    n|=n>>8
    n|=n>>16
    return n-(n>>1)
def GCD(x, y): 
    x=abs(x)
    y=abs(y)
    if(min(x,y)==0):
        return max(x,y)
    while(y): 
        x, y = y, x % y 
    return x
def pref(a,n):             #preSum array
    pre=[0]*n
    pre[0]=a[0]
    for i in range(1,n):
        pre[i]=a[i]+pre[i-1]
    return pre
##def Divisors(n) : #list of divisors
##    l = []  
##    for i in range(1, int(math.sqrt(n) + 1)) :
##        if (n % i == 0) : 
##            if (n // i == i) : 
##                l.append(i) 
##            else : 
##                l.append(i)
##                l.append(n//i)
##    return l
prime1=[]
def SieveOfEratosthenes(n): #list of primes upto n
    global prime1
    prime1 = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime1[p] == True): 
            for i in range(p * p, n+1, p): 
                prime1[i] = False
        p += 1
    f=[]
    for p in range(2, n): 
        if prime1[p]: 
            f.append(p)
    return f
prime=[]
def Sieve(bo):
    global prime
    prime = [1 for i in range(bo)] 
    p = 2
    while (p<bo): 
        if (prime[p] == 1): 
            for i in range(p,bo, p): 
                prime[i] = p
        p += 1
    f=[]
    for p in range(2, n): 
        if prime[p]==1: 
            f.append(p)
    return f
vi=[0]*(200005)
adj=[[] for i in range(200005)]
def dfs(node,ans):
    vi[node]=1
    ans+=[node+1]
    for j in adj[node]:
        if(vi[j]==0):
            dfs(j,ans)
    return ans

# https://github.com/cheran-senthil/PyRival/blob/master/pyrival/misc/bootstrap.py
def bootstrap(f, stack=[]):   #write @bootstrap before recursive func
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
 
    return wrappedfunc
def Divisors(n) : #list of divisors
    c=0 
    for i in range(1, int(math.sqrt(n) + 1)) :
        if (n % i == 0) : 
            if (n // i == i) : 
                c+=1
            else :
                c+=2
    return c
"""*******************************************************"""
def main():
    n,x,m=cin();f=0
    if(x==0):
        ans=0
    else:
        nmod=x%m
        store=[nmod];su=nmod
        d=dd(int);d[nmod]=1;x=nmod*nmod
        for i in range(1,n):
            if(x==0):
                f=1
                break
            elif(d[x]==0):
                nmod=x%m
                x=nmod*nmod
                d[nmod]=i+1
                store+=[nmod]
                su+=nmod
            else:
                f=2
                cont=d[x%m]-1
                rem=n-i
                break
        if(f<=1):
            ans=su
        else:
    ##        print(store)
            
            nval=len(store)-cont
            remsum=sum(store[cont:])
            mul=rem//nval
            modu=rem%nval
    ##        print(rem,cont,nval,mul,modu,len(store))
            k=sum(store[cont:(cont+modu)])
            ans=su+mul*remsum+k
    print(ans)
##    dp = np.full(10**5+1, 10**18, dtype=np.int64)
    
######## Python 2 and 3 footer by Pajenegod and c1729
 
# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.
 
# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
 
import os, sys
from io import IOBase, BytesIO
 
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'
 
# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'R' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'R' [0]:
        A.append(sign*numb)
    return A
 
# threading.Thread(target=main).start()
if __name__== "__main__":
  main()

Submission status: Runtime Error

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

a = [x] + [0]*(n-1)
sum = 0

print('a=')
print(a)

for i in range (0,n-1):
    a[i+1] = (a[i]**2) % m
    sum += a[i]
else:
    sum += a[n-1]

print(sum)

Submission status: Runtime Error

Solution code:
n, x, m = map(int,input().split())
lst = [0 for i in range(m)]
lst2 = [x]
i = 2
lst[x] = 1
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)
        break
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)

Submission status: Runtime Error

Solution code:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

func StrStdin() string {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	return strings.TrimSpace(scanner.Text())
}

// 1つの符号付き整数値(64bit)入力
// Exapmle:
// ------------------
// 1000000007
// ------------------
func Int64Stdin() int64 {
	stringInput := StrStdin()
	num, _ := strconv.ParseInt(strings.TrimSpace(stringInput), 10, 64)
	return num
}

// 1つの符号なし整数値(64bit)入力
// Exapmle:
// ------------------
// 1000000007
// ------------------
func Uint64Stdin() uint64 {
	stringInput := StrStdin()
	num, _ := strconv.ParseUint(strings.TrimSpace(stringInput), 10, 64)
	return num
}

// 1つの符号付き浮動小数点数(64bit)の入力
// Exapmle:
// ------------------
// 33.4
// ------------------
func Float64Stdin() float64 {
	stringInput := StrStdin()
	num, _ := strconv.ParseFloat(strings.TrimSpace(stringInput), 64)
	return num
}

// 空白や空文字だけの値を除去したSplit
func SplitWithoutEmpty(stringTargeted string, delim string) []string {
	stringSplited := strings.Split(stringTargeted, delim)
	strs := []string{}

	for _, str := range stringSplited {
		if str != "" {
			strs = append(strs, str)
		}
	}
	return strs
}

// 空白区切りで複数の文字列を1行で入力
// Example:
// --------------------
// hoge fuga hage
// --------------------
func SliceStrsStdin(delim string) []string {
	stringInput := StrStdin()
	return SplitWithoutEmpty(stringInput, delim)
}

// 空白区切りで複数の符号付き整数値(64bit)を1行で入力
// Example:
// --------------------
// 45 -100 23
// --------------------
func SliceInt64Stdin() []int64 {
	stringSplited := SliceStrsStdin(" ")

	int64Slice := []int64{}

	for ni := range stringSplited {
		num, _ := strconv.ParseInt(stringSplited[ni], 10, 64)
		int64Slice = append(int64Slice, num)
	}

	return int64Slice
}

// 空白区切りで複数の符号なし整数値(64bit)を1行で入力
// Example:
// --------------------
// 43 7 21
// --------------------
func SliceUint64Stdin() []uint64 {
	stringSplited := SliceStrsStdin(" ")

	uint64Slice := []uint64{}

	for ni := range stringSplited {
		num, _ := strconv.ParseUint(stringSplited[ni], 10, 64)
		uint64Slice = append(uint64Slice, num)
	}

	return uint64Slice
}

// 空白区切りで複数の符号付き浮動小数点数(64bit)を入力
// Example:
// --------------------
// 45.0 -62.1 11.7
// --------------------
func SliceFloat64Stdin() []float64 {
	stringSplited := SliceStrsStdin(" ")

	float64Slice := []float64{}

	for ni := range stringSplited {
		num, _ := strconv.ParseFloat(stringSplited[ni], 64)
		float64Slice = append(float64Slice, num)
	}

	return float64Slice
}
func main() {
	var (
		N, X, M, S, i int
		n             float64
	)

	x := SliceInt64Stdin()
	N = int(x[0])
	X = int(x[1])
	M = int(x[2])
	S = X
	n = float64(X)
	for i = 1; i < N; i++ {
		n = float64(int(math.Pow(n, 2.0)) % M)
		S = S + int(n)
	}

	fmt.Print(S)

}

Submission status: Runtime Error

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

lst = set()
num = []
for i in range(1, n + 1):
    lst.add(x), num.append(x)
    x = x ** 2 % m
    if x in lst:
        break
cnt, idx = i, num.index(x)
div, mod = divmod(n - cnt, len(num) - idx)
ans = sum(num[:idx + mod])
ans += sum(num[idx:]) * (div + 1)
print(ans)

Submission status: Runtime Error

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

count = X
bef = X
_sum = [X]
dic = {X: 1}

for i in range(1, N + 1):
    bef = pow(bef, 2, M)
    if bef in dic:
        posi = dic[bef]
        l = len(_sum) - posi
        plus = _sum[-1] - (_sum[posi - 1] if posi - 1 > 0 else 0)
        count += plus * ((N - i) // l)
        mod = ((N - i) % l)
        count += _sum[posi - 1 + mod] - (_sum[posi - 1] if posi - 1 > 0 else 0)
        break
    else:
        dic.setdefault(bef, i)
        _sum.append(bef + _sum[-1])
    count += bef

print(count)

Submission status: Runtime Error

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

num_list = []
num2 = x

for i in range(n) :
    try :
        num1 = num2 % m
        if num1 in num_list :
            num = num_list.index(num1)
            break
        else :
            num_list.append(num1)
        num2 = num1 ** 2
    except ZeroDivisionError :
        break

if num_list == [] :
    print(0)
else :
    acc1 = sum(num_list[:num])
    acc2 = sum(num_list[num:])
    
    num3 = n // len(num_list[num:])
    num4 = n % len(num_list[num:])
    print(acc1 + acc2 * num3 + sum(num_list[num : num4]))

Submission status: Runtime Error

Solution code:
 

        
n,x,m=map(int,input().split())
l=[]
ll=set()
num=x
for i in range(min(n,10**5)):
    if num in ll:
        break
    else:
        ll.add(num)
        l.append(num)
        num=num**2%m
k1=len(l)
k2=l.index(num)
if k1>=n:
    print(sum(l))
else:
    k3=n-k1
    sum4=sum(l[k1:k2])
    k4=k3//(k1-k2)
    k5=k1+(k1-k2)*k4
    print(sum(l)+k4*sum4+sum(l[k5:n]))

Submission status: Runtime Error

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

ans = x % m
dicNum = dict()
dicSum = dict()
dicNum[x] = 1
dicSum[1] = x

for i in range(2,n+1):
    b = x
    x = x**2 % m
    if x in dicNum.keys():
        t = i - dicNum[x]
        zan = n - i + 1
        k = zan // t
        ans += (dicSum[i-1] - dicSum[dicNum[x]-1]) * k
        if zan% t != 0:
            zan = zan % t
            ans += dicSum[dicNum[x] - 1 + zan] - dicSum[dicNum[x]-1]
        break
    else:
        ans += x
        dicSum[i] = ans
        dicNum[x] = i

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate

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

num_list = []
num2 = x

for i in range(n) :
    try :
        num1 = num2 % m
        if num1 in num_list :
            num = num_list.index(num1)
            break
        else :
            num_list.append(num1)
        num2 = num1 ** 2
    except ZeroDivisionError :
        break

if num_list == [] :
    print(0)
else :
    acc1 = list(accumulate(num_list[:num]))[-1]
    acc2 = list(accumulate(num_list[num:]))[-1]
    
    num3 = n // len(num_list[num:])
    num4 = n % len(num_list[num:])
    print(acc1 + acc2 * num3 + sum(num_list[num : num4]))

Submission status: Runtime Error

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

ans = x % m
#dic = dict()
dicNum = dict()
dicSum = dict()
dicNum[x] = 1
dicSum[1] = x

if n > 10000:
    for i in range(2,n+1):
        b = x
        x = x**2 % m
        if x in dicNum.keys():
            t = i - dicNum[x]
            zan = n - i + 1
            k = zan // t
            ans += (dicSum[i-1] - dicSum[dicNum[x]-1]) * k
            if zan% t != 0:
                zan = zan % t
                ans += dicSum[dicNum[x] - 1 + zan] - dicSum[dicNum[x]-1]
            break
        else:
            ans += x
            dicSum[i] = ans
            #dic[x] = ans
            dicNum[x] = i

else:
    for i in range(2,n+1):
        x = x**2 % m
        ans += x
        dicSum[i] = ans
        #dic[x] = ans
        dicNum[x] = i

print(ans)

Submission status: Runtime Error

Solution code:
n, x, m = map(int,input().split())
ans = x
num = 0
l = [0]*n
lis = [-1]*n
l[0] = x
lis[x] = num
for i in range(1,n):
    x = (x*x)%m
    num += 1
    if lis[x]!=-1:
        a = (n-i)//(i-lis[x])
        b = (n-i)%(i-lis[x])
        ans += a * sum(l[lis[x]:i])
        break
    l[i] = x
    lis[x] = i
    ans += x
for i in range(lis[x],lis[x]+b):
    ans += l[i]
print(ans)

Submission status: Runtime Error

Solution code:
n, x, m = map(int,input().split())
ans = x
num = 0
l = [0]*1000
lis = [-1]*1000
l[0] = x
lis[x] = num
for i in range(1,n):
    x = (x*x)%m
    num += 1
    if lis[x]!=-1:
        a = (n-i)//(i-lis[x])
        b = (n-i)%(i-lis[x])
        ans += a * sum(l[lis[x]:i])
        break
    l[i] = x
    lis[x] = i
    ans += x
for i in range(lis[x],lis[x]+b):
    ans += l[i]
print(ans)

Submission status: Runtime Error

Solution code:

import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
##import operator
input=sys.stdin.readline
import random
##sys.setrecursionlimit(10**6)
##fo=open("output1.txt","w")
##fi=open("input1.txt","w")
mod=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())

    
for _ in range(1):
    n,x,m=cin();f=0
    if(x==0):
        ans=0
    else:
        nmod=x%m
        store=[nmod]
        d=dd(int);d[nmod]=1;x=nmod*nmod
        for i in range(1,n):
            if(x==0):
                f=1
                break
            elif(d[x]==0):
                nmod=x%m
                x=nmod*nmod
                d[nmod]=1
                store+=[nmod]
            else:
                f=2
                cont=store.index(x%m)
                rem=n-i
                break
        if(f<=1):
            print(sum(store))
        else:
    ##        print(store)
            
            nval=len(store)-cont
            remsum=sum(store[cont:])
            mul=rem//nval
            modu=rem%nval
    ##        print(rem,cont,nval,mul,modu,len(store))
            k=sum(store[cont:(cont+modu)])
            ans=sum(store)+mul*remsum+k
    print(ans)
        
        
        
        
            
    
    

    
    
        
        
      
    

##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far

Submission status: Runtime Error

Solution code:
n, x, m = map(int,input().split())
ans = x
num = 0
l = [0]*min(m,10**4)
lis = [-1]*min(m,10**4)
l[0] = x
lis[x] = num
for i in range(1,n):
    x = (x*x)%m
    num += 1
    if lis[x]!=-1:
        a = (n-i)//(i-lis[x])
        b = (n-i)%(i-lis[x])
        ans += a * sum(l[lis[x]:i])
        break
    l[i] = x
    lis[x] = i
    ans += x
for i in range(lis[x],lis[x]+b):
    ans += l[i]
print(ans)

Submission status: Runtime Error

Solution code:
n, x, m = map(int,input().split())
ans = x
num = 0
l = [0]*m
lis = [-1]*m
l[0] = x
lis[x] = num
for i in range(1,n):
    x = (x*x)%m
    num += 1
    if lis[x]!=-1:
        a = (n-i)//(i-lis[x])
        b = (n-i)%(i-lis[x])
        ans += a * sum(l[lis[x]:i])
        break
    l[i] = x
    lis[x] = i
    ans += x
for i in range(lis[x],lis[x]+b):
    ans += l[i]
print(ans)