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())

now = X
used = [X]
i = 1
T = True
while T:
  if i == N:
    print(sum(used))
    quit()
  else:
    next_ = now * now % M
    if next_ in used:
      T = False
    else:
      used.append(next_)
      now = next_
    i += 1  

count = used.index(next_)
ans = sum(used[:count])
#print(ans)
roop = len(used) - count
roop_ans = sum(used[count:])
#print(roop, roop_ans)
index = (N - count) % roop
#print(index)
ans += roop_ans * int((N - count) // roop)
#print(ans)
if index == 0:
  index = roop
  
ans += sum(used[count:count + index]) 
  
print(ans)
#print(used)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
a = []
a.append(x)
for i in range(1, n):
        a.append((x  % m) ** 2)
        x= a[i]

print(sum(a))

Submission status: Wrong Answer

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

def ans(a):
    x_2 = (a ** 2) % m
    return(x_2)

re = 2

for i in range(n - 1):
    #print(x)
    x = ans(x)

    re += x
    #print("ans" + str(re))

print(re)

Submission status: Wrong Answer

Solution code:
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

####
MOD = 998244353
YES, NO, IMP = "YES", "NO", "IMPOSSIBLE"
from collections import defaultdict as ddic


def solve(N, X, M):
    seen = {X: 0}
    t = 0
    while True:
        t += 1
        if t == N:
            return sum(seen)
        X2 = X*X%M
        if X2 not in seen:
            seen[X2] = t
            X = X2
            continue
        break

    base = sum(seen)
    N -= t
    u = seen[X2]
    mu = t - u
    period = sum(k for k,v in seen.items() if v >= u)
    Q, R = divmod(N, mu)
    base += Q * period

    while R:
        base += X
        X *= X
        X %= M
        R -= 1

    return base
    
print solve(*rrm())

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,raw_input().split()) 
v=[x] 
t={x:1} 
while True: 
    y=(x*x)%m 
    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 
print ans

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
nxt = [-1] * m
now = x
while nxt[now] == -1:
    nxt[now] = now * now % m
    now = nxt[now]
junction = now
ans = x
now = x
n = n - 1
while n and now != junction:
    now = nxt[now]
    n -= 1
    ans += now
if n == 0:
    print(ans)
    exit()

llen = 1
lsum = junction
now = nxt[junction]
while now != junction:
    now = nxt[now]
    llen += 1
    lsum += now
ans += lsum * (n // llen)
n = n % llen

now = junction
while n:
    now = nxt[now]
    n -= 1
    ans += now
print(ans)

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:
        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:
n,x,m=map(int,raw_input().split()) 
v=[x] 
t={x:1} 
while True: 
    y=(x*x)%m 
    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 
print ans

Submission status: Wrong Answer

Solution code:
N,X,M = map(int,input().split(" "))
q = [-1] * (M + 1)
A = X
i = 0
su = []

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())
exist = [0] * (m+1)
ans = 0
imamade = []
cnt = 0
for i in range(n):
    if exist[x] == 1:
        ans += x
        break
    else:
        exist[x] = 1
        imamade.append(x)
        x *= x
        x %= m
        cnt += 1
    if i == n-1:
        print(sum(imamade))
        exit()
num = imamade.index(x)
n -= num
ans += sum(imamade[:num]) + sum(imamade[num:]) * (n // (cnt-num))
n %= (cnt-num)
for i in range(n-1):
    x *= x
    x %= m
    ans += x
print(ans)

Submission status: Wrong Answer

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

ans = 0
A = []
T = [-1]*M
i = 0
f = False
while i<N:
  A += [X]
  if T[X]!=-1 and not f:
    f = True
    ans += sum(A[T[X]:-1])*((N-i)//(i-T[X])) + X
    i += (N-i)//(i-T[X])*(i-T[X]) + 1
    X = X*X%M
    continue
  T[X] = i
  ans += X
  X = X*X%M
  i += 1
print(ans)

Submission status: Wrong Answer

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

vis = [-1] * m
sq = [(i*i)%m for i in range(m)]

cur = x
for i in range(n):
  if vis[cur] >= 0:
    break
  vis[cur] = i
  cur = (cur*cur)%m

# print(vis)

cycle = max(vis) - vis[cur] + 1

ans = 0
for i in range(min(n, vis[cur])):
  ans += x
  x = (x*x)%m
if n <= vis[cur]:
  print(ans)
else:
  rem = n - vis[cur]
  cyclesum = 0
  y = x
  for i in range(cycle):
    cyclesum += y
    y = (y*y)%m
  total = rem//cycle
  extra = rem - cycle*total
  ans += cyclesum*total
  for i in range(extra):
    ans += y
    y = (y*y)%m
  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-1):
    a = a ** 2 % m
    if a == 0:
        zero = 1
        break
    if a == x:
        break
    lm.append(a)

if zero == 1:
    print(sum(lm))

else:
    k = len(lm)

    s = n // k
    r = n % k

    slm = sum(lm)

    print(slm * s + sum(lm[:r]))

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:
        break
    else:
        exist[x] = 1
        imamade.append(x)
        x *= x
        x %= m
        cnt += 1
    if i == n-1:
        print(sum(imamade))
        exit()
num = imamade.index(x)
n -= num
ans = sum(imamade[:num]) + sum(imamade[num:]) * (n // (cnt-num))
n %= (cnt-num)
for i in range(n-1):
    x *= x
    x %= m
    ans += x
print(ans)

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
a=[x]
su=x
s={x}
for i in range(n):
  x=(x**2)%m
  if x in s:
    n-=i+1
    a=a[a.index(x):]
    l=len(a)
    su+=sum(a)*(n//l)
    n-=(n//l)*l
    su+=sum(a[:n])
    print(su)
    exit()
  a.append(x)
  su+=x
  s.add(x)
print(su)

Submission status: Wrong Answer

Solution code:
N,X,M = map(int,input().split())
R = [X]
dr = {}
for i in range(M):
    dr[i] = 0
m = min(N,M)
for i in range(m):
    r = R[-1]
    r = r**2%M
    if dr[r] == 1:
        break
    R.append(r)
    dr[r] = 1
for i in range(len(R)):
    if r == R[i]:
        break

Submission status: Wrong Answer

Solution code:
N,X,M = map(int,input().split())
R = [X]
m = min(N,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

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
loop = [X]
appeared = set(loop)
while True:
  n = loop[-1] ** 2 % M
  if n in appeared:
    break
  else:
    loop.append(n)
    appeared.add(n)
i = loop.index(n)
preloop = loop[:i]
loop = loop[i:]
if N <= len(loop):
  print(sum(loop[:N]))
  exit()

total = sum(preloop)
N -= len(preloop)
total += sum(loop) * (N // len(loop))
for l, _ in zip(loop, range(N % len(loop))):
  total += l
print(total)

Submission status: Wrong Answer

Solution code:
n,x,m = map(int, input().split())
ai = x
tmp = [ai]
used = set(tmp)
for i in range(n):
    nxt = ai**2 % m
    if nxt in tmp:
        break
    tmp.append(nxt)
    ai = nxt
if len(tmp) == n:
    ans = sum(tmp)
    print(ans)
    exit()

rem = n-len(tmp)
first = tmp.index(nxt)
ans = 0
l = []
for i in range(len(tmp)):
    if i < first:
        ans += tmp[i]
    else:
        l.append(tmp[i])
m = len(l)
x,y = divmod(rem, m)
ans += sum(l)*x
for i in range(y):
    ans += l[i]
print(ans)

Submission status: Time Limit Exceeded

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

ans=X

for i in range(N-1):
    nx=table[i]**2
    nx%=M
    if nx in table:
        first=table.index(nx)
        oneloop=i+1-first
        rest=N-i-1
        loops=rest//oneloop
        totalofoneloop=sum(table[first:])
        ans+=totalofoneloop*loops
        remain=rest%oneloop
        ans+=sum(table[first:first+remain])
        print(ans)
        exit()
    else:
        table.append(nx)
        ans+=nx
 

print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

res = 0
a = X
appeared = []
circle = []
index = [-1] * M
for i in range(N):
    if index[a] >= 0:
        for j in range(index[a], i):
            circle.append(appeared[j])
            break

    index[a] = i
    appeared.append(a)
    res += a
    a = pow(a, 2, M)

N -= len(appeared)
if N == 0:
    print(res)
    exit()

accm = [0] * (len(circle) + 1)
for i in range(len(circle)):
    accm[i + 1] = accm[i] + circle[i]

q = N // len(accm)
r = N % len(accm)
res += accm[-1] * q + accm[r]

print(res)

Submission status: Time Limit Exceeded

Solution code:
N,X,M = map(int,input().split())
dps = [X%M]
rt = 0
while True:
  d = (dps[-1]**2)%M
  if d not in dps:
    dps.append(d)
    if N == len(dps):
      print(sum(dps))
      break
  else:
    ki = dps.index(d)
    RP = (N-ki) // len(dps[ki:])
    mod = (N-ki) % len(dps[ki:])
    print(sum(dps[:ki]) + RP*sum(dps[ki:])+sum(dps[ki:ki+mod]))
    break

Submission status: Time Limit Exceeded

Solution code:
N,X,M = map(int,input().split())
dps = [X%M]
rt = 0
while True:
  d = (dps[-1]**2)%M
  if d not in dps:
    dps.append(d)
  else:
    ki = dps.index(d)
    break
RP = (N-ki) // len(dps[ki:])
mod = (N-ki) % len(dps[ki:])
rt = sum(dps[:ki]) + RP*sum(dps[ki:])+sum(dps[ki:ki+mod])
print(rt)

Submission status: Time Limit Exceeded

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

f=1
w=[]
d=[0]*(m+2)
t=[0]
chk=n
for i in range(m+1):
    f=pow(2,i)
    p=pow(x,f,m)
    if d[p]: break
    d[p]=1
    w.append(p)
    t.append(t[-1]+p)
    #f*=2
    chk-=1
    if chk==0:
        print(t[-1])
        exit()
ans=0
a=w.index(p)
ans+=t[a]
n-=a
loo=len(w)-a
if n%loo==0:
    ans+=(t[-1]-t[a])*(n//loo)
else:
    ans+=(t[-1]-t[a])*(n//loo)
    ans+=t[a+n%loo]-t[a]
print(ans)

Submission status: Time Limit Exceeded

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

f=1
w=[]
d=set([])
t=[0]
chk=n
#while 1:
for i in range(m+1):
    f=pow(2,i)
    p=pow(x,f,m)
    if p in d: break
    d.add(p)
    w.append(p)
    t.append(t[-1]+p)
    #f*=2
    chk-=1
    if chk==0:
        print(t[-1])
        exit()
ans=0
a=w.index(p)
ans+=t[a]
n-=a
loo=len(w)-a
if n%loo==0:
    ans+=(t[-1]-t[a])*(n//loo)
else:
    ans+=(t[-1]-t[a])*(n//loo)
    ans+=t[a+n%loo]-t[a]
print(ans)

Submission status: Time Limit Exceeded

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

f=1
w=[]
d=set([])
t=[0]
chk=n
while 1:
    p=pow(x,f,m)
    if p in d: break
    d.add(p)
    w.append(p)
    t.append(t[-1]+p)
    f*=2
    chk-=1
    if chk==0:
        print(t[-1])
        exit()
ans=0
a=w.index(p)
ans+=t[a]
n-=a
loo=len(w)-a
if n%loo==0:
    ans+=(t[-1]-t[a])*(n//loo)
else:
    ans+=(t[-1]-t[a])*(n//loo)
    ans+=t[a+n%loo]-t[a]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
n, x, m = map(int, input().split())

tmp = x 
cnt = 0 
dup = 0 
a = [x] 
while True:
    tmp = (tmp*tmp)%m
    if tmp in a:
        dup = tmp 
        break
    cnt += 1
    a.append(tmp)

di = 0 
for i in range(len(a)):
    if a[i] == dup:
        di = i 

# block sum
b = []
bs = 0 
for i in range(di, len(a)):
    bs += a[i]
    b.append(a[i])

# block length
bl = len(a)-di
sumbl = 0 

ans = 0 
for i in range(di):
    ans += a[i]
ans += (n-di)//bl * bs
for i in range((n-di)%bl):
    ans += b[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def my_func(n, x, m):
    if n == 1:
        return x
    elif n == 2:
        b = x ** 2 % m
        return b
    else:
        y = (x ** 2 % m)
        for j in range(n-2):
            y = y ** 2 % m

        #b = my_func(n-1, x, m) ** 2 % m
        #b = (x ** 2 % m) ** 2 % m
        return y

if __name__ == "__main__":


    n,x,m = (int(k) for k in input().split())

    ans = 0

    #print(sys.getrecursionlimit())

    for i in range(1, n+1):
        ans += my_func(i,x,m)

    print(ans)

Submission status: Time Limit Exceeded

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

for n in range(N - 1):
        tmp = a[n]*a[n]%  M
        if(tmp == 0):
                break
        a.append(tmp)

print(sum(a))

Submission status: Time Limit Exceeded

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

logn = (10**10).bit_length()
doubling = []
sumd = []
for _ in range(logn):
  tmpd = [-1] * m
  doubling.append(tmpd)
  tmps = [0] * m
  sumd.append(tmps)

for i in range(m):
  doubling[0][i] = i * i % m
  sumd[0][i] = i

for i in range(1,logn):
  for j in range(m):
    doubling[i][j] = doubling[i-1][doubling[i-1][j]]
    sumd[i][j] = sumd[i-1][j] + sumd[i-1][doubling[i-1][j]]

now = x
pos = 0
result = 0
while n:
  if n & 1:
    result += sumd[pos][now]
    now = doubling[pos][now]
  n = n >> 1
  pos += 1

print(result)

Submission status: Time Limit Exceeded

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

def main():
  N,X,M=map(int,pin().split())
  A=X
  d=[X]
  su=X
  for i in range(N-1):
    A=(A**2)%M
    if A in d:
      t=d.index(A)
      T=N-i-1
      d=d[t:]
      l=len(d)
      su+=sum(d)*(T//l)
      T=T%(T//l)
      su+=sum(d[:T])
      print(su)
      return
    d.append(A)
    su+=A
  print(su)
  return
main()

Submission status: Time Limit Exceeded

Solution code:
N, X, M = [int(i) for i in input().split()]
mods = [X]
start = None
for i in range(N-1):
  X = X*X % M
  if X not in mods:
    mods.append(X)
  else:
    start = mods.index(X)
    break
spec, period = mods[:start], mods[start::]
N -= len(spec)
S = sum(spec)
S += sum(period)*(int(N/len(period))) + sum(period[:N%len(period):])
print(S)

Submission status: Time Limit Exceeded

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

a = x
list1 = [a]
for i in range(1,m+1):
  a = a*a % m
  if a in list1:
    index1 = i
    index2 = list1.index(a)
    
    break
  else:    
    list1.append(a)

s = sum(list1[index2:index1])
d = index1 - index2
if s != 0:
  sx = (n - index2) // d
  sr = (n - index2) % d

  ans = sum(list1[:index2]) + s * sx +sum (list1[index2:index2+sr])
else:
  ans = sum(list1[:index2])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int, input().split()) 
ans = 0
x_list = []

for _ in range(min(10**5,n)):
    x_list.append(x)
    ans += x
    x = x**2 % m
    if x_list.count(x) == 1:
        after_list = x_list[x_list.index(x):(len(x_list))]
        if x_list.index(x) == 0:
            if (n // len(x_list)) == 0:
                ans = ans * (n // len(x_list))
            else:
                ans = ans * (n // len(x_list)) + sum(x_list[0:((n % len(x_list)))])
        else:
            if (n-x_list.index(x)) % len(after_list) == 0:
                ans = (ans - sum(x_list[0:(x_list.index(x))])) * ((n-x_list.index(x)) // len(after_list)) + sum(x_list[0:(x_list.index(x))])
            else:
                ans = (ans - sum(x_list[0:(x_list.index(x))])) * ((n-x_list.index(x)) // len(after_list)) + sum(after_list[0:(((n-x_list.index(x)) % len(after_list)))]) + sum(x_list[0:(x_list.index(x))])
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int, input().split()) 
ans = 0
x_list = []

for _ in range(min(10**5,n)):
    x_list.append(x)
    ans += x
    x = x**2 % m
    if x == 0:
        break
    if x == 1:
        ans = ans + (n-len(x_list))
        break
    if x_list.count(x) == 1:
        after_list = x_list[x_list.index(x):(len(x_list))]
        if x_list.index(x) == 0:
            if (n // len(x_list)) == 0:
                ans = ans * (n // len(x_list))
            else:
                ans = ans * (n // len(x_list)) + sum(x_list[0:((n % len(x_list)))])
        else:
            if (n-x_list.index(x)) % len(after_list) == 0:
                ans = (ans - sum(x_list[0:(x_list.index(x))])) * ((n-x_list.index(x)) // len(after_list)) + sum(x_list[0:(x_list.index(x))])
            else:
                ans = (ans - sum(x_list[0:(x_list.index(x))])) * ((n-x_list.index(x)) // len(after_list)) + sum(after_list[0:(((n-x_list.index(x)) % len(after_list)))]) + sum(x_list[0:(x_list.index(x))])
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int, input().split()) 
ans = 0
x_list = []

for _ in range(n):
    x_list.append(x)
    ans += x
    x = x**2 % m
    if x == 0:
        break
    if x == 1:
        ans = ans + (n-len(x_list))
        break
    if x_list.count(x) == 1:
        after_list = x_list[x_list.index(x):(len(x_list))]
        if x_list.index(x) == 0:
            if (n // len(x_list)) == 0:
                ans = ans * (n // len(x_list))
            else:
                ans = ans * (n // len(x_list)) + sum(x_list[0:((n % len(x_list)))])
        else:
            if (n-x_list.index(x)) % len(after_list) == 0:
                ans = (ans - sum(x_list[0:(x_list.index(x))])) * ((n-x_list.index(x)) // len(after_list)) + sum(x_list[0:(x_list.index(x))])
            else:
                ans = (ans - sum(x_list[0:(x_list.index(x))])) * ((n-x_list.index(x)) // len(after_list)) + sum(after_list[0:(((n-x_list.index(x)) % len(after_list)))]) + sum(x_list[0:(x_list.index(x))])
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int, input().split()) 
ans = 0
x_list = []

for _ in range(n):
    x_list.append(x)
    ans += x
    x = x**2 % m
    if x == 0:
        break
    if x == 1:
        ans = ans + (n-len(x_list))
        break
    if x_list.count(x) == 1:
        after_list = x_list[x_list.index(x):(len(x_list))]
        if x_list.index(x) == 0:
            if (n // len(x_list)) == 0:
                ans = sum(x_list) * (n // len(x_list))
            else:
                ans = sum(x_list) * (n // len(x_list)) + sum(x_list[0:((n % len(x_list)))])
        else:
            if (n-x_list.index(x)) % len(after_list) == 0:
                ans = sum(after_list) * ((n-x_list.index(x)) // len(after_list)) + sum(x_list[0:(x_list.index(x))])
            else:
                ans = sum(after_list) * ((n-x_list.index(x)) // len(after_list)) + sum(after_list[0:(((n-x_list.index(x)) % len(after_list)))]) + sum(x_list[0:(x_list.index(x))])
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int, input().split()) 
ans = 0
x_list = []

for _ in range(n):
    x_list.append(x)
    ans += x
    x = x**2 % m
    if x == 0:
        ans = sum(x_list)
        break
    if x == 1:
        ans = sum(x_list) + (n-len(x_list))
        break
    if x_list.count(x) == 1:
        after_list = x_list[x_list.index(x):(len(x_list))]
        if x_list.index(x) == 0:
            if (n // len(x_list)) == 0:
                ans = sum(x_list) * (n // len(x_list))
            else:
                ans = sum(x_list) * (n // len(x_list)) + sum(x_list[0:((n % len(x_list)))])
        else:
            if (n-x_list.index(x)) % len(after_list) == 0:
                ans = sum(after_list) * ((n-x_list.index(x)) // len(after_list)) + sum(x_list[0:(x_list.index(x))])
            else:
                ans = sum(after_list) * ((n-x_list.index(x)) // len(after_list)) + sum(after_list[0:(((n-x_list.index(x)) % len(after_list)))]) + sum(x_list[0:(x_list.index(x))])
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int, input().split()) 
ans = 0
x_list = []

for _ in range(n):
    x_list.append(x)
    x = x**2 % m
    if x == 0:
        ans = sum(x_list)
        break
    if x == 1:
        ans = sum(x_list) + (n-len(x_list))
        break
    if x_list.count(x) == 1:
        after_list = x_list[x_list.index(x):(len(x_list))]
        if x_list.index(x) == 0:
            if (n // len(x_list)) == 0:
                ans = sum(x_list) * (n // len(x_list))
            else:
                ans = sum(x_list) * (n // len(x_list)) + sum(x_list[0:((n % len(x_list)))])
        else:
            if (n-x_list.index(x)) % len(after_list) == 0:
                ans = sum(after_list) * ((n-x_list.index(x)) // len(after_list)) + sum(x_list[0:(x_list.index(x))])
            else:
                ans = sum(after_list) * ((n-x_list.index(x)) // len(after_list)) + sum(after_list[0:(((n-x_list.index(x)) % len(after_list)))]) + sum(x_list[0:(x_list.index(x))])
        break

if ans == 0 and not x == 0:
    ans = sum(x_list)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int, input().split()) 
ans = 0
x_list = []

for _ in range(n):
    x_list.append(x)
    x = x**2 % m
    if x == 0:
        ans = sum(x_list)
        break
    if x_list.count(x) == 1:
        after_list = x_list[x_list.index(x):(len(x_list))]
        if x_list.index(x) == 0:
            if (n // len(x_list)) == 0:
                ans = sum(x_list) * (n // len(x_list))
            else:
                ans = sum(x_list) * (n // len(x_list)) + sum(x_list[0:((n % len(x_list)))])
        else:
            if (n-x_list.index(x)) % len(after_list) == 0:
                ans = sum(after_list) * ((n-x_list.index(x)) // len(after_list)) + sum(x_list[0:(x_list.index(x))])
            else:
                ans = sum(after_list) * ((n-x_list.index(x)) // len(after_list)) + sum(after_list[0:(((n-x_list.index(x)) % len(after_list)))]) + sum(x_list[0:(x_list.index(x))])
        break

if ans == 0 and not x == 0:
    ans = sum(x_list)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, X, M = map(int, input().split())
check = [0]*(M+1)
check[X] += 1
A = X
last_count = 0
while True:
    A = (A**2)%M
    if check[A] != 0:
        last_count = sum(check)
        target_value = A
        break
    check[A] += 1
A2 = X
first_count = 0
while True:
    first_count += 1
    A2 = (A2**2)%M
    if A2 == target_value:
        break

roop_count = last_count-first_count
A3 = target_value
mass = A3
for i in range(roop_count-1):
    A3 = (A3**2)%M
    mass += A3
if roop_count == 0:
    A = X
    ans = X
    for i in range(N-1):
        A = (A**2)%M
        ans += A
    print(ans)
    exit()

ans = X
A = X
for i in range(min(N,first_count)-1):
    A = (A**2)%M
    ans += A
if N > first_count:
    ans += ((N-first_count)//roop_count)*mass
    A4 = target_value
    if (N-first_count)%roop_count >= 1:
        ans += A4
    for i in range(((N-first_count)%roop_count)-1):
        A4 = (A4**2)%M
        ans += A4

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- using utf8 -*-
import sys
inputlinevec = sys.stdin.readline().strip().split(' ')
n = int(inputlinevec[0])
x = int(inputlinevec[1])
m = int(inputlinevec[2])

sum_res = x
crcle_list = list()
crcle_idx = 0
pre_a = x

for idx in range(1, n):
    #a范围在0-m之间，不会无限递增，因此很大概率会重复
    #a * a % m这种单变量的式子，一旦a出现了之前出现过的值
    #后续就会出现重复的序列，然后循环
    this_a = (pre_a * pre_a) % m
    pre_a = this_a
    
    if this_a not in crcle_list:
        crcle_list.append(this_a)
        sum_res = sum_res + this_a
    else:
        crcle_step = len(crcle_list) - crcle_list.index(this_a)
        remain_crcle = int((n - idx) / crcle_step)
        remain_crcle_tail = int((n - idx) % crcle_step)
        
        crcle_sum = 0
        crcle_sum_tail = 0
        for a_item in crcle_list[crcle_list.index(this_a):]:
            crcle_sum = crcle_sum + a_item
            remain_crcle_tail = remain_crcle_tail - 1
            if remain_crcle_tail == 0:
                crcle_sum_tail = crcle_sum
        sum_res = sum_res + (remain_crcle * crcle_sum) + crcle_sum_tail
        break
        
    
print(sum_res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

n,x,m = (int(i) for i in input().split())
l = np.array([x])
ans = x
memo_array = [-1]*(m+1)

for i in range(1,n):
    ans = ans**2%m
    idx = memo_array[ans]
    if idx != -1:
        loop_num, mod = divmod((n-idx),(i-idx))
        print(np.sum(l[:idx]) + np.sum(l[idx:])*(loop_num)+np.sum(l[idx:idx+mod]))
        sys.exit()
    l = np.append(l,ans)
    memo_array[ans]=i
print(np.sum(l))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

n,x,m = (int(i) for i in input().split())
l = np.array([x])
ans = x
for i in range(n-1):
    ans = ans**2%m
    if ans in l:
        loop_start = int(np.where(l==ans)[0])
        loop_num, mod = divmod((n-loop_start),(i-loop_start+1))
        print(np.sum(l[:loop_start]) + np.sum(l[loop_start:])*(loop_num)+np.sum(l[loop_start:loop_start+mod]))
        sys.exit()
    l = np.append(l,ans)
print(np.sum(l))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

n,x,m = (int(i) for i in input().split())
l = np.array([x])
for i in range(n-1):
    ans = (l[i])**2%m
    if ans in l:
        loop_start = int(np.where(l==ans)[0])
        loop_num, mod = divmod((n-loop_start),(i-loop_start+1))
        print(np.sum(l[:loop_start]) + np.sum(l[loop_start:])*(loop_num)+np.sum(l[loop_start:loop_start+mod]))
        sys.exit()
    l = np.append(l,ans)
print(np.sum(l))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

n,x,m = (int(i) for i in input().split())
l = np.array([x])
for i in range(n-1):
    ans = (l[i])**2%m
    if ans in l:
        b = int(np.where(l==ans)[0])
        print(np.sum(l[:b]) + np.sum(l[b:])*((n-b)//(i-b+1))+np.sum(l[b:b+(n-b)%(i-b+1)]))
        sys.exit()
    else:
        l = np.append(l,ans)
print(np.sum(l))

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
arr = [x]
mod = x

def find_value(lst, value):
    return [i for i, x in enumerate(lst) if x == value]

ans = 0
for i in range(n-1):
    mod = mod ** 2 % m
    res = find_value(arr, mod)

    if res: 
        j = res[0]
        a = i + 1 - j
        q, mod = divmod((n - j), a)
        ans = sum(arr[0:j]) + q * sum(arr[j:j+a]) + sum(arr[j:j+mod])
        break
    arr.append(mod)

if ans == 0:
    ans = sum(arr)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int,input().split())
#listを2つ使って初項からループ手前までのセット、そして二回目のループのセット。
k_1 = list()
k_2 = list()
#len(k_2)でも良かった
#loop_sumはk_2によって表されるループの和
loop_number = 0
loop_sum = 0
while x not in k_1:
	k_1.append(x)
	x = x*x%m
while x not in k_2:
	k_2.append(x)
	loop_number+=1
	loop_sum+=x 
	x = x*x%m
ans = 0
for i in range(len(k_1)):
	ans +=  k_1[i]
ans = ans + loop_sum * ((n-len(k_1))//loop_number)
for i in range((n-len(k_1))%loop_number):
	ans += k_2[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int,input().split())
mod = m
num = []
ans = 0
cnt = 0
ch = x
while True:
    if ch not in num:
        num.append(ch)
    else:
        st = ch #ループの開始している配列の初めの数字
        break
    ch *= ch
    ch %= mod
for i in range(len(num)):
    if num[i] == st:
        stnum = i #ループ開始の最初の配列のの番号
        #print("重なり始め =",stnum)
        break
else:
    stnum = len(num) - 1
if 0 in num:
    ans = sum(num[:n])
else:
    #print("len(num) =",len(num),"stnum =",stnum)
    if (len(num)-stnum) != 0:
        rest = (n-stnum)%(len(num)-stnum)
        sho = (n-stnum)//(len(num)-stnum)
        #print("rest =",rest,"sho =",sho)
    else:
        rest = n
        sho = 0
    if n <= stnum + 1:
        ans = sum(num[:n])
    else:
        ans = sum(num[:stnum]) + sum(num[stnum:stnum+rest]) + sum(num[stnum:])*sho
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,X,M=list(map(int,input().split()))
C=[]
C.append(X)
for i in range(min(N,M+4)):
    t=(C[i]**2)%M
    if t not in C:
        C.append(t)
        k=N
        L=1
    else:
        k=C.index(t)
        L=i-k+1
        break

Cinitial=C[0:k]
Crepeat=C[k:]
sumCrepeat=sum(Crepeat)
sumCinitial=sum(Cinitial)
S=(N-k)//L
print(sumCinitial+sumCrepeat*S+sum(Crepeat[i] for i in range((N-k)%L)))

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
result = [x]
for i in range(m):
    y = (result[-1] * result[-1]) % m
    if y in result:
        start = result.index(y)
        end = i
        break
    result.append(y)

loop = result[start:]
a = start
b = (n - a) // len(loop)
c = (n - a) % len(loop)
ans = sum(result[:a]) + (sum(loop) * b) + sum(loop[:c])
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
A =[x]
B=[]
a = x
for i in range(n-1):
    a = a**2 % m
    if a in A:
        num_s = A.index(a)
        num_e = i+1
        break
    A.append(a)
#print(num_s, num_e)       
#print(A)
s =0
if len(A) != n:
    for i in range(num_s):
        s += A[i]
    
    kai = (n-num_s)//(num_e-num_s)
    kai_s = (n-num_s)%(num_e-num_s)
    
    cy = 0
    for i in range(num_s, num_e):
        cy += A[i]
    
    s += cy*kai
    
    for i in range(num_s, num_s+kai_s):
        s += A[i]
else:
    s = sum(A)
print(s)

Submission status: Time Limit Exceeded

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

y=x
A=[]
A.append(y)
cnt=1
su=x

for i in range(m):
    y=(y**2)%m
    cnt+=1
    if y in A:
        break
    else:
        A.append(y)
        su+=y

c=A.index(y) #周期のはじめ
d=cnt-(c+1)  #周期のはじめから次の周期のはじめで個数を求める

e=sum(A[:c]) 
#周期に入るまえまでを足しておく

f=0
for w in range((n-c)%d):
    f+=A[c:][w]
    #周期からはみでた最後の部分

g=su-e#1周期分
h=g*((n-c)//d)#かけざん

print(e+h+f)

Submission status: Time Limit Exceeded

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

y=x
A=[]
A.append(y)
cnt=1

for i in range(m):
    y=(y**2)%m
    cnt+=1
    if y in A:
        break
    else:
        A.append(y)

c=A.index(y) #周期のはじめ
d=cnt-(c+1)  #周期のはじめから次の周期のはじめで個数を求める

e=sum(A[:c]) 
#周期に入るまえまでを足しておく

f=0
for w in range((n-c)%d):
    f+=A[c:][w]
    #周期からはみでた最後の部分

g=sum(A[c:])#1周期分
h=g*((n-c)//d)#かけざん

print(e+h+f)