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:
 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, len(li))) * q
              + sum(li[i] for i in range(s, s + r)))

Submission status: Runtime Error

Solution code:
N,X,M=map(int,input().split())
F=(N-1).bit_length()

A=[[0]*M for _ in range(F)]

for x in range(M):
    A[0][x]=(x*x)%M

for d in range(1,F):
    for x in range(M):
        A[d][x]=A[d-1][A[d-1][x]]

S=[[0]*M for _ in range(F)]
for x in range(M):
    S[0][x]=A[0][x]

for d in range(1,F):
    for x in range(M):
        S[d][x]=S[d-1][x]+S[d-1][A[d-1][x]]

Ans=0
depth=0
N-=1
Y=X
while N>0:
    if N%2:
        Ans+=S[depth][X]
        X=A[depth][X]
    depth+=1
    N>>=1
print(Ans+Y)

Submission status: Runtime Error

Solution code:
n=int(input())
x=int(input())
m=int(input())
a=x
sum=x
for i in range(2,n+1):
  a=a*a%m
  sum=sum+a
 
print(sum)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
a=list()
ans=0
for i in range(n):
    ans+=x
    a.append(x)
    x=(x**2)%m
    if x in a:
        s=a.index(x)
        break

sum=0
for i in range(s, len(a)):
    sum+=a[i]

ans+=sum*(((n-s)//(len(a)-s))-1)

z=(n-s)%(len(a)-s)
for i in range(z):
    ans+=a[s]
    s+=1
print(ans)

Submission status: Runtime Error

Solution code:
N,X,M=map(int,input().split())
l=[X]
p=[-1]*(M+1)
p[X]=0
for i in range(N-1):
    x=(l[-1]**2)%M
    if p[x]>=0:
        break
    l.append(x)
    p[x]=i+1
x=p[x]
y=len(l)-x
print(sum(l[:x])+(N-x)//y*sum(l[x:])+sum(l[x:x+(N-x)%y]))

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
lis = [0]*M
lis[0] = X
check = [-1]*M
check[X] = 0
for i in range(1,M):
  lis[i] = pow(lis[i-1],2,M)
  if check[lis[i]]>=0:
    cyc = i-check[lis[i]]
    start = check[lis[i]]
    break
  check[lis[i]] = i
from itertools import groupby, accumulate, product, permutations, combinations
cum = list(accumulate(lis))
cyc_cum = cum[-1]-cum[start]
if N<=start:
  ans = cum[N-1]
else:
  ans = cyc_cum*((N-start)//cyc)+cum[(N-start)%cyc+start-1]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
readline=sys.stdin.readline

N,X,M = map(int,readline().split())
route = [X]
dic = {}
first = []
loop = []
for i in range(1, N):
  X = (X ** 2) % M
  if X in dic:
    first = route[:dic[X]]
    loop = route[dic[X]:]
    break
  route.append(X)
  dic[X] = i

if N == len(first):
  print(sum(first))
elif N < len(first):
  print(sum(first[:N]))
else:
  ans = sum(first)
  one_loop = sum(loop)
  N -= len(first)
  loop_cnt = N // len(loop)
  rest = N % len(loop)
  ans += loop_cnt * (sum(loop))
  ans += sum(loop[:rest])

  print(ans)

Submission status: Runtime Error

Solution code:
def pow(x, n, m):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
            K %= m
        x *= x
        x %= m
        n //= 2

    return (K * x) % m

def main():
    import sys
    st=set()
    N,X,M=list(map(int,sys.stdin.readline().split()))
    L=[]
    a=-1
    for i in range(N):
        a=pow(X,2**i,M)
        if a in st:
            break
        else:
            st.add(a)
            L.append(a)

    n=N
    er
    if a+1:
        idx=L.index(a)
        res=sum(L[:idx])
        n-=idx

        s=sum(L[idx:])
        length=len(L)-idx
        res+=s*(n//length)
        res+=(sum(L[idx:idx+n%length]))
        print(res)
    else:
        print(sum(N))



main()

Submission status: Runtime Error

Solution code:
import sys
readline=sys.stdin.readline

N,X,M = map(int,readline().split())
route = [X]
dic = {}
first = []
loop = []
for i in range(1, 10000):
  X = (X ** 2) % M
  if X in dic:
    first = route[:dic[X]]
    loop = route[dic[X]:]
    break
  route.append(X)
  dic[X] = i

#print(first)
#print(loop)

if N == len(first):
  print(sum(first))
elif N < len(first):
  print(sum(first[:N]))
else:
  ans = sum(first)
  one_loop = sum(loop)
  N -= len(first)
  loop_cnt = N // len(loop)
  rest = N % len(loop)
  ans += loop_cnt * (sum(loop))
  ans += sum(loop[:rest])

  print(ans)

Submission status: Runtime Error

Solution code:


def solve(N,X,M):
    memo = [-1]*(M+3)
    acc = [0]*(M+4)
    x = X
    for i in range(M):
        if memo[x] >= 0:
            break
        acc[i+1] = acc[i]+x
        memo[x] = i
        x = (x*x)%M


    end = i
    start = memo[x]
    cycle = end - start

    if N < end:
        return acc[N]

    cycle_sum = acc[end]-acc[start]

    res = acc[start]

    N -= start
    res += (N//cycle)*cycle_sum
    res += acc[start+(N%cycle)]-acc[start]
    return res


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

Submission status: Runtime Error

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

for i in range(1,m):
  rem[i] = (rem[i - 1] ** 2) % m
  chk[rem[i - 1] ** 2 % m] += 1
  if chk[rem[i - 1] ** 2 % m] > 1:
    temp1 = rem[i - 1] ** 2 % m
    temp2 = i
    break

for i in range(m):
  if rem[i] == temp1:
    temp3 = i
    break

num = (n - temp3) // (temp2 - temp3)   

S = sum(rem[:temp3]) + sum(rem[temp3:temp2]) * num + sum(rem[temp3:n - (num * (temp2 - temp3))])
print(S)

Submission status: Runtime Error

Solution code:
N,X,M = map(int,input().split())
A = [0]*M
S = 0
r = X
A[r-1] = 1
d = 0
for i in range(1,M):
    r = (r*r) % M
    if A[r-1] == 0:
        A[r-1] = i+1
    else:
        I = A[r-1]
        j = i+1
        d = j-I
        break
r = X
for i in range(I):
    S += r
    r = (r*r) % M
if d != 0:
    t,u = (N-I)//d,(N-I)%d
    s = 0
    for i in range(d):
        s += r
        r = (r*r) % M
    S += s*t
    for i in range(u):
        S += r
        r = (r*r) % M
print(S)

Submission status: Runtime Error

Solution code:
from math import inf, log2


class SegmentTree:
    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size : self.size+self.n] = array
        for i in range(self.size-1, -1, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def query(self, alpha, omega):
        """Returns the result of function over the range (inclusive)!"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """Updates the element at index to given value!"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index >>= 1


# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        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")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    #n = int(input())
    n, x, m = map(int, input().split())
    #a, b = map(int, input().split())
    #c, d = map(int, input().split())
    #a = list(map(int, input().split()))
    #b = list(map(int, input().split()))
    ans = x
    st = set()
    from collections import deque
    a = deque([])
    xc = x
    n -= 1
    i = -1
    for i in range(n):
        xc = (xc * xc) % m
        if xc in st:break
        a += [xc]
        st.add(xc)
    if i != n-1:
        while a[0] != xc and n:
            ans += a.popleft()
            n -= 1
    total = sum(a)
    ans += (total * ((n)//(len(a))))
    for i in range((n) % len(a)):
        ans = (ans + a[i])
    print(ans)

Submission status: Runtime Error

Solution code:


def solve(N,X,M):
    memo = [-1]*M
    acc = [0]*(M+1)
    x = X%M
    for i in range(M):
        if memo[x] >= 0:
            break
        acc[i+1] = acc[i]+x
        memo[x] = i
        x = (x*x)%M


    end = i
    start = memo[x]
    cycle = end - start

    if N < end:
        return acc[N]+(X - X%M)

    cycle_sum = acc[end]-acc[start]

    res = acc[start]+(X - X%M)

    N -= start
    res += (N//cycle)*cycle_sum
    res += acc[start+(N%cycle)]-acc[start]
    return res

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

Submission status: Runtime Error

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

yj=[x]

for i in range(n):
  an=(yj[i]**2)%m
  if an in yj:
    lps=yj.index(an)
    break
  yj.append(an)
  
blp=yj[:lps]
lp=yj[lps:]
ans=sum(blp)+sum(lp)*((n-len(blp))//len(lp))+sum(lp[:(n-len(blp))%len(lp)])
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N,X,M = map(int,input().split())
R = [X]
m = min(X,M)
for i in range(m):
    r = R[-1]
    r = r**2%M
    if r in R:
        break
    R.append(r)
for i in range(len(R)):
    if r == R[i]:
        break
a = 0
b = sum(R)
for j in range(i):
    a += R[j]
    b -= R[j]
n = len(R) - i
t = N - i
p = t // n
q = t % n
c = 0
for j in range(q):
    c += R[i+j]
ans = a + b*p + c
print(ans)

Submission status: Runtime Error

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