TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.  Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.  You are given an integer K that is less than or equal to 10, and K non- intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]. Let S be the union of these K segments. Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.    * When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.  To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Submission attempts (in order):
n,k = tuple(map(int,input().split()))
boolean = [False for _ in range(n+1)]
for _ in range(k):
  l,r = tuple(map(int,input().split()))
  for num in range(l,r+1):
    boolean[num] = True;
FINAL = [i for i in range(len(boolean)) if boolean[i]]
dp = [0 for _ in range(n+1)]
for i in range(2,n+1):
  for lower in FINAL:  #optimized!
    if boolean[lower]:  #start + lower
      start = i - lower
      if start >= 1:
      	dp[i]+= dp[start]
print(dp[n]%998244353)

n,k = tuple(map(int,input().split()))
boolean = [False for _ in range(n+1)]
for _ in range(k):
  l,r = tuple(map(int,input().split()))
  for num in range(l,r+1):
    boolean[num] = True;
dp = [0 for _ in range(n+1)]
for i in range(2,n+1):
  for lower in range(1,i):
    if boolean[lower]:  #start + lower
      start = i - lower
      dp[i]+= dp[start]
print(dp[n]%998244353)
    


'''go to every index and then run a index - 1 to 1 for it and check whether the proposed number lies somewhere or not'''
n,k = tuple(map(int,input().split()))
boolean = [False]*n
for _ in range(k):
  l,r = tuple(map(int,input().split()))
  for num in range(l,r+1):
    boolean[num] = True;
dp = [0 for _ in range(n+1)]
boolean = [False for _ in range(n+1)]
for i in range(2,n+1):
  for lower in range(1,i):
    if boolean[lower]:
    	start = i - lower
        dp[i] += dp[start]
print(dp[n])
    

MOD = 998244353
N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(K)]
 
dp = [0] * (N+1)
dp[1] = 1    #ok
for i in range(1, N):
  dp[i] += dp[i-1]   #as min k = 1, so carry this on to the next
  dp[i] %= MOD
  for l, r in LR:
    ll = i + l
    rr = i + r
    if ll <= N:
      dp[ll] += dp[i]    #yes ll is accesible
      dp[ll] %= MOD
    if rr < N:
      dp[rr+1] -= dp[i]    #not accessible and will get cancelled out when we take prefix sum
      dp[rr+1] %= MOD
 
print(dp[-1])

Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Accepted
Problem: There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.  Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.  You are given an integer K that is less than or equal to 10, and K non- intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]. Let S be the union of these K segments. Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.    * When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.  To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Submission attempts (in order):
import numpy as np

n, k = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(k)]
mod = 998244353

s.sort()

dp = np.zeros(n * 2)
dp[1] = 1

for i in range(1, n):
    for l, r in s:
        dp[i + l:i + r + 1] += dp[i]
        dp[i + l:i + r + 1] %= mod

print(dp[n] % mod)


n, k = map(int, input().split())
mod = 998244353
lr = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (n + 10)
dp[1] = 1
cumsum = [0] * (n + 10)
cumsum[1] = 1

for i in range(2, n + 1):
    for l, r in lr:
        if l >= i:
            continue

        ll = max(1, i - r)
        rr = i - l
        dp[i] += cumsum[rr] - cumsum[ll - 1]
        dp[i] %= mod
    cumsum[i] = cumsum[i - 1] + dp[i]
    cumsum[i] %= mod

print(dp[n] % mod)


Verdicts: Wrong Answer

Accepted
Problem: There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.  Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.  You are given an integer K that is less than or equal to 10, and K non- intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]. Let S be the union of these K segments. Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.    * When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.  To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Submission attempts (in order):
N,K=map(int,input().split())
x=998244353
S=[]
for i in range(K):
    l,r=map(int,input().split())
    S.append(l)
    S.append(r)
S=list(set(S))
dp=[0 for i in range(N)]
print(S)
for i in range(N):
    for j in range(len(S)):
        if(i-S[j]>0):
            dp[i]+=dp[i-S[j]]
            dp[i]=dp[i]%x
        elif(i-S[j]==0):
            dp[i]+=1
            dp[i]=dp[i]%x
print(dp)

N,K=map(int,input().split())
x=998244353
dp=[0 for i in range(N)]
sdp=[0 for i in range(N)]
L=[]
R=[]
dp[0]=1
sdp[0]=1
for i in range(K):
    l,r=map(int,input().split())
    L.append(l)
    R.append(r) 
for i in range(1,N):
    for j in range(K):
        dp[i]+=(sdp[max(i-L[j],-1)]-sdp[max(i-R[j]-1,-1)])
        dp[i]%=x
    sdp[i]=(sdp[i-1]+dp[i])%x
print(dp[-1]%x)

Verdicts: Wrong Answer

Accepted
Problem: There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.  Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.  You are given an integer K that is less than or equal to 10, and K non- intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]. Let S be the union of these K segments. Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.    * When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.  To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Submission attempts (in order):
n, k = map(int, input().split())
MOD = 998244353

lr = []
for _ in range(k):
    l, r = map(int, input().split())
    lr += (list(range(l, r + 1)))

lr.sort()
lr = np.array(lr)

dp = np.zeros(n + n, dtype=np.int64)
dp[0] = 1
dp2 = dp.copy()

for i in range(n):
    idx = i + lr
    dp2[idx] += dp[i]
    dp2 %= MOD
    dp = dp2

print(dp[n - 1])

def solve(l, r, i):
    if i - l < 1:
        return 0
    return dp[i - l] - dp[max(i - r - 1, 0)]


n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]
MOD = 998244353

dp = [0] * (n + 1)
dp[1] = 1

for i in range(2, n + 1):
    tmp = 0
    for l, r in lr:
        tmp += solve(l, r, i)
    tmp = tmp % MOD
    dp[i] = (dp[i - 1] + tmp) % MOD

print(tmp)

Verdicts: Runtime Error

Accepted
Problem: There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.  Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.  You are given an integer K that is less than or equal to 10, and K non- intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]. Let S be the union of these K segments. Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.    * When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.  To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Submission attempts (in order):
mod = 998244353


def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)]     
    A = [0 if n != 0 else 1 for n in range(N)]      

    for i in range(1, N):   
        for l, r in S:  
            if i - l < 0:   
                break
            else:           
                dp[i] += A[i-l] - A[max(i-r-1, 0)]  
        dp[i] %= mod
        A[i] = (A[i-1] + dp[i]) % mod
    print(dp, A)

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = {tuple(map(int, input().split())) for k in range(K)}
    S = sorted(list(S), key = lambda x:x[0])    
    main(N, S)

mod = 998244353


def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)]     
    A = [0 if n != 0 else 1 for n in range(N)]      

    for i in range(1, N):   
        for l, r in S:  
            if i - l < 0:   
                break
            else:           
                dp[i] += A[i-l] - A[max(i-r-1, 0)]  
        dp[i] %= mod
        A[i] = (A[i-1] + dp[i]) % mod
    print(dp[-1])

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = {tuple(map(int, input().split())) for k in range(K)}
    S = sorted(list(S), key = lambda x:x[0])    
    main(N, S)

mod = 998244353




def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)]     
    A = [0 if n != 0 else 1 for n in range(N)]      

    for i in range(1, N):   
        for l, r in S:  
            if i - l < 0:   
                break
            else:           
                if i - r <= 0:  
                    dp[i] += A[i-l]
                else:
                    dp[i] += A[i-l] - A[i-r-1]
        dp[i] %= mod
        A[i] = (A[i-1] + dp[i]) % mod
    print(dp[-1])

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = {tuple(map(int, input().split())) for k in range(K)}
    S = sorted(list(S), key = lambda x:x[0])    
    main(N, S)

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.  Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.  You are given an integer K that is less than or equal to 10, and K non- intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]. Let S be the union of these K segments. Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.    * When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.  To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Submission attempts (in order):
from numba import jit

import sys
sys.setrecursionlimit(10**9)

N, K = map(int, input().split())
S = set()

MOD = 998244353
for _ in range(K):
    L, R = map(int, input().split())
    S |= set(range(L, R + 1))
# print(f'{S=}')

DP = [-1] * (N + 1)
DP[0] = 0
DP[1] = 1


@njit
def f(idx):
    ans = 0
    for s in S:
        if idx - s < 0:
            continue
        if DP[idx - s] == -1:
            DP[idx - s] = f(idx - s)
        ans += DP[idx - s]
    return ans % MOD


ans = f(N)
# print(f'{DP=}')
print(ans)


from numba import njit

import sys
sys.setrecursionlimit(10**9)

N, K = map(int, input().split())
S = set()

MOD = 998244353
for _ in range(K):
    L, R = map(int, input().split())
    S |= set(range(L, R + 1))
# print(f'{S=}')

DP = [-1] * (N + 1)
DP[0] = 0
DP[1] = 1


@njit
def f(idx):
    ans = 0
    for s in S:
        if idx - s < 0:
            continue
        if DP[idx - s] == -1:
            DP[idx - s] = f(idx - s)
        ans += DP[idx - s]
    return ans % MOD


ans = f(N)
# print(f'{DP=}')
print(ans)


N, K = map(int, input().split())
MOD = 998244353
LR = []
for _ in range(K):
    L, R = map(int, input().split())
    LR.append((L, R))
# print(f'{LR=}')

DP = [0] * (N + 1)
DP[1] = 1
S = [0] * (N + 1)

for i in range(1, len(DP)):
    for L, R in LR:
        v = S[max(i - L, 0)] - S[max(i - R - 1, 0)]
        DP[i] += v
    DP[i] %= MOD
    S[i] = (S[i - 1] + DP[i]) % MOD

# print(f'{DP=}')
# print(f'{S=}')
print(DP[-1])


Verdicts: Runtime Error

Runtime Error

Accepted
Problem: There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.  Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.  You are given an integer K that is less than or equal to 10, and K non- intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]. Let S be the union of these K segments. Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.    * When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.  To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Submission attempts (in order):
mod = 998244353
n, k = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(k)]
dp = [0 for i in range(n + 1)]
dp[0] = 1
cum = [0, 1]
cur = [0 for i in range(k)]
for i in range(1, n + 1):
    cnt = 0
    for j in range(k):
        r = (i - (lr[j][1] - lr[j][0] + 1))
        l = r - (lr[j][1] - lr[j][0])
        print(l, r, cum)
        if l <= 0:
            continue
        cnt += cum[r] - cum[l - 1]
    dp[i] = dp[i - 1] + cnt
    cum.append(cnt + cum[-1])
print(dp[n])

mod = 998244353
n, k = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(k)]
for i in range(k):
    lr[i][1] += 1
dp = [0] * n
dp[0] = 1
for i in range(1, n):
    dp[i] += dp[i - 1]
    if i == 1:
        dp[1] = 0
    for l, r in lr:
        if i - l >= 0:
            dp[i] += dp[i - l]
        if i - r >= 0:
            dp[i] -= dp[i - r]
    dp[i] %= mod
print(dp[n - 1])

Verdicts: Runtime Error

Accepted
Problem: There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.  Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.  You are given an integer K that is less than or equal to 10, and K non- intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]. Let S be the union of these K segments. Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.    * When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.  To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Submission attempts (in order):
import sys
readline=sys.stdin.readline

import numpy as np
from numba import njit,i8

N,K=map(int,readline().split())
DIV = 998244353
steps = []
for i in range(K):
  l,r = map(int,readline().split())
  for j in range(l, r + 1):
    steps.append(j)
    
steps = sorted(steps)
steps = np.array(steps, dtype = int)

@njit(i8(i8[:]),cache = True)
def solve(steps):
  dp = np.zeros(N, dtype = int)
  dp[0] = 1
  for i in range(len(dp)):
    for s in steps:
      if i + s >= len(dp):
        break
      dp[i + s] += dp[i]
      dp[i + s] %= DIV
      
  return dp[-1]

print(solve())


import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
DIV = 998244353

L = [None] * K
R = [None] * K
for i in range(K):
  L[i],R[i] = map(int,readline().split())

dp = [0] * (N + 1)
sdp = [0] * (N + 1)
dp[1] = 1
sdp[1] = 1
  
for i in range(2, len(dp)):
  for j in range(K):
    li = max(i - R[j], 0)
    ri = i - L[j]
    if ri < 0:
      continue
    dp[i] += (sdp[ri] - sdp[li - 1])
    dp[i] %= DIV
  sdp[i] = sdp[i - 1] + dp[i]
  sdp[i] %= DIV
  
print(dp[N])

Verdicts: Runtime Error

Accepted
Problem: There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.  Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.  You are given an integer K that is less than or equal to 10, and K non- intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]. Let S be the union of these K segments. Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.    * When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.  To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Submission attempts (in order):
import collections
import math
import sys
sys.setrecursionlimit(10**7)
inf=998244353


N,K=map(int,input().split())
SS=[]

for i in range(K):
    s1,s2=map(int,input().split())
    for j in range(s1,s2+1):
        SS.append(j)

# Driver program to test above function 

table = [0 for k in range(N-1)] 

for s in SS:
    if s<N-1:
        table[s-1]+=1
for i in range(0,N-1):
    for s in SS:
        if i+s<N-1:
            table[i+s]+=table[i]
            table[i+s]%=inf
print(table[-1]%inf)


inf=998244353


N,K=map(int,input().split())
SS=[list(map(int,input().split())) for i in range(K)]

SS.sort()

table = [0 for k in range(N)] 
diff = [0 for k in range(N-1)]

table[0]=1
diff[0]=-1

for i in range(N-1):
    if table[i]!=0:
        for s in SS:
            lef=s[0]
            rig=s[1]
            if i+lef-1<N-1:
                diff[i+lef-1]+=table[i]
            if i+rig<N-1:
                diff[i+rig]-=table[i]
    table[i+1]=table[i]+diff[i]
    table[i+1]%=inf

print(table[N-1])

Verdicts: Wrong Answer

Accepted
Problem: There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.  Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.  You are given an integer K that is less than or equal to 10, and K non- intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]. Let S be the union of these K segments. Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.    * When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.  To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Submission attempts (in order):
# import sys


# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, K, LR):
    mod = 998244353
    S = []
    for lr in LR:
        S += [i for i in range(lr[0], lr[1] + 1)]
    S.sort()
    dp = [0] * (N + 1)
    dp[1] = 1
    for i in range(1, N + 1):
        for s in S:
            if i + s > N:
                break
            dp[i + s] = (dp[i + s] + dp[i]) % mod
    print(dp[N])


if __name__ == '__main__':
    # N, K = map(int, input().split())
    # LR = [[int(i) for i in input().split()] for _ in range(K)]
    # solve(N,K,LR)

    # test
    from random import randint
    from func import random_str

    N, K = 2 * 10 ** 5, 1
    LR = [[1, N]]
    solve(N, K, LR)






# import sys


# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, K, LR):
    mod = 998244353
    dp = [0] * (N + 1)
    dp[1] = 1
    
    
    
    
    dp[2] = 1 if 1 in [lr[0] for lr in LR] else 0
    for i in range(3, N + 1):
        x = 0
        for l, r in LR:
            x += dp[max(i - l, 0)] - dp[max(i - 1 - r, 0)]
        dp[i] = (dp[i - 1] + x) % mod
    print(dp[N])


if __name__ == '__main__':
    N, K = map(int, input().split())
    LR = [[int(i) for i in input().split()] for _ in range(K)]
    solve(N, K, LR)

    # # test
    # from random import randint
    # from func import random_str
    # N, K = 2 * 10 ** 5, 1
    # LR = [[1, N]]
    # solve(N, K, LR)


Verdicts: Runtime Error

Accepted
Problem: There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.  Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.  You are given an integer K that is less than or equal to 10, and K non- intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]. Let S be the union of these K segments. Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.    * When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.  To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Submission attempts (in order):
N, K = map(int, input().split())
S = []
for i in range(K):
    L, R = map(int, input().split())
    S += list(range(L, R+1))

dp = [0] * N
dp[0] = 1

S.sort()

for i in range(1, N):
    for s in S:
        if i - s < 0:break
        dp[i] = (dp[i] + dp[i - s]) % 998244353

print(dp)

print(dp[-1])

mod = 998244353
N, K = map(int, input().split())

S = []
for i in range(K):
    L, R = map(int, input().split())
    S.append((L, R))

dp = [0] * (N+1)
dpsum = [0] * (N+1)
dp[1] = 1
dpsum[1] = 1

for i in range(2, N+1):
    for s in S:
        l = i - s[1]
        r = i - s[0]
        if r < 1:continue
        l = max(1, l)

        dp[i] += dpsum[r] - dpsum[l-1]
        dp[i] %= mod

    dpsum[i] = (dpsum[i-1] + dp[i]) % mod

print(dp[-1])


Verdicts: Wrong Answer

Accepted
Problem: 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}.

Submission attempts (in order):
N, X, M = map(int, input().split())

ans = X
x = X

C = [0, x]
Xd = [-1] * (M+1)
Xd[x] = 0
Xl = [x]

for i in range(1, N):
    x = x**2 % M

    if Xd[x] > -1:
        break
    Xd[x] = i
    Xl.append(x)
    ans += x
    C.append(ans)

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

ans = 0
C = [0]
Xd = [-1] * (M+1)

for i in range(N):
    x = X if i==0 else x**2 % M
    
    if Xd[x] > -1:
        break
    Xd[x] = i
    ans += x
    C.append(ans)

loop_len = i - Xd[x]
if loop_len > 0:
    S = C[i] - C[Xd[x]]
    loop_num = (N - i) // loop_len
    ans += loop_num * S
    m = N - loop_num * loop_len - i
    ans += C[Xd[x]+m] - C[Xd[x]]

print(ans)

Verdicts: Wrong Answer

Accepted
Problem: 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}.

Submission attempts (in order):
n,x,m=map(int,input().split())
l=[0 for i in range(m)]
ans=0
y=[]
i=1
flag=0
ys=n
while i<n:
    if flag==0:
        ans+=x
    l[x]+=1
    x=x*x%m
    i+=1
    if l[x]==2 and flag==0:
        flag=1
        ys=i
    if flag:
        if l[x]==3:
            break
        y.append(x)
if len(y):
    p,pp=divmod(n-ys,len(y))
    print(ans+p*sum(y)+sum(y[:pp+1]))
    #print(ans,p*sum(y),sum(y[:pp+1]))
else:
    print(ans)

n,x,m=map(int,input().split())
l=[0 for i in range(m)]
ans=0
y=[]
i=1
flag=0
ys=n
while i<n:
    if flag==0:
        ans+=x
    l[x]+=1
    x=x*x%m
    i+=1
    if l[x]==2 and flag==0:
        flag=1
        ys=i
    if flag:
        if l[x]==3:
            break
        y.append(x)
if len(y):
    p,pp=divmod(n-ys,len(y))
    print(ans+p*sum(y)+sum(y[:pp+1]))
    print(ans,p*sum(y),sum(y[:pp+1]))
else:
    print(ans)

n,x,m=map(int,input().split())
l=[0 for i in range(m)]
ans=0
y=[]
i=1
flag=0
ys=n
while i<n+1:
    if flag==0:
        ans+=x
    l[x]+=1
    x=x*x%m
    i+=1
    if l[x]==2 and flag==0:
        flag=1
        ys=i
    if flag:
        if l[x]==3:
            break
        y.append(x)
if len(y):
    p,pp=divmod(n-ys,len(y))
    print(ans+p*sum(y)+sum(y[:pp+1]))
    #print(ans,p*sum(y),sum(y[:pp+1]))
else:
    print(ans)

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: 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}.

Submission attempts (in order):
n,x,m=map(int,input().split())

a_i = x
log = [x]
app=[-1]*m
app[x]=0
last = x
for i in range(1,n):
  a_i = (a_i**2)%m
  if app[a_i] > -1:
    last = a_i
    break
  app[a_i] = i
  log.append(a_i)


ans = sum(log[:min(n, app[last])])
if n > app[last]:
  
  ans += sum(log[app[last]:]) * ((n-app[last]) // (len(log) - app[last]))
  
  ans += sum(log[app[last]:app[last] + (n-app[last]) % (len(log) - app[last])])
print(ans)
print(*log)

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

a_i = x
log = [x]
app=[-1]*m
app[x]=0
last = x
for i in range(1,n):
  a_i = (a_i**2)%m
  if app[a_i] > -1:
    last = a_i
    break
  app[a_i] = i
  log.append(a_i)


ans = sum(log[:min(n, app[last])])
if n > app[last]:
  
  ans += sum(log[app[last]:]) * ((n-app[last]) // (len(log) - app[last]))
  
  ans += sum(log[app[last]:app[last] + (n-app[last]) % (len(log) - app[last])])
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: 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}.

Submission attempts (in order):
n,x,m=map(int,input().split())
l=[-1]*m
s=[0]*m
t=p=0
while l[x]<0:
  t+=1
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
  print(t,x,s[p])
T=t+1-l[x]
print(T)
S=s[p]+x-s[x]
print(S)
if n<l[x]:
  print(s[l.index(n)])
else:
  print(S*((n-l[x])//T)+s[l.index(l[x]+(n-l[x])%T)])

n,x,m=map(int,input().split())
l,s=[0]*m,[0]*m
t=p=0
while l[x]<1:
  t+=1
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=p*p%m
k=l[x]
d,m=divmod(n-k,t+1-k)
print((s[p]+x-s[x])*d+s[l.index(k+m)])

Verdicts: Wrong Answer

Accepted
Problem: 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}.

Submission attempts (in order):
N, X, M = map(int, input().split())
dp = [False]*(M+1)
dp[X] = True
S = [0]*(M+1)
S[1] = X
tmp = X
for i in range(2, M+1):
    tmp = pow(tmp, 2, M)
    if dp[tmp]:
        for j in range(i):
            if tmp == S[j]:
                break
        ans = 0
        for k in range(j, i):
            ans += S[k]
        ans *= (N-j-1)//(i-j)
        for k in range(1, j):
            ans += S[k]
        for k in range(j, j+(N-j-1)%(i-j)):
            ans += S[k]
        print(ans)
        break
    else:
        dp[tmp] = True
        S[i] = tmp
else:
    print(sum(S))


N, X, M = map(int, input().split())
dp = [False]*(M+1)
dp[X] = True
S = [0]*(M+1)
S[1] = X
tmp = X
for i in range(2, min(M+1, N+1)):
    tmp = pow(tmp, 2, M)
    if dp[tmp]:
        for j in range(1, i):
            if tmp == S[j]:
                break
        ans = 0
        for k in range(j, i):
            ans += S[k]
        ans *= (N-j+1)//(i-j)
        for k in range(1, j):
            ans += S[k]
        for k in range(j, j+(N-j+1)%(i-j)):
            ans += S[k]
        print(ans)
        break
    else:
        dp[tmp] = True
        S[i] = tmp
else:
    print(sum(S))

Verdicts: Wrong Answer

Accepted
Problem: 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}.

Submission attempts (in order):
N, X, M = map(int, input().split())

nxt = X
lst = []
dic = {}

for i in range(M):
    if nxt in dic:
        loop_st = dic[nxt]
        loop_ed = i - 1
        break

    lst.append(nxt)
    dic[nxt] = i

    nxt = (nxt ** 2) % M


v = N - loop_st
q, r = divmod(v, loop_ed - loop_st + 1)

pre_sum = sum(lst[:loop_st])
loop_sum = q * sum(lst[loop_st:])
post_sum = sum(lst[loop_st:loop_st + r])


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

nxt = X
lst = []
dic = {}

for i in range(M + 1):
    if nxt in dic:
        loop_st = dic[nxt]
        loop_ed = i - 1
        break

    lst.append(nxt)
    dic[nxt] = i

    nxt = (nxt ** 2) % M


v = N - loop_st
q, r = divmod(v, loop_ed - loop_st + 1)

pre_sum = sum(lst[:loop_st])
loop_sum = q * sum(lst[loop_st:])
post_sum = sum(lst[loop_st:loop_st + r])
print(pre_sum + loop_sum + post_sum)


Verdicts: Runtime Error

Accepted
Problem: 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}.

Submission attempts (in order):
# -*- coding: utf-8 -*-

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

A=[0]*M
A[0]=X
D=[0]*M

s=N
for i in range(1,N):
    a=A[i-1]**2%M
    if D[a] == 1:
        s=A.index(a)
        break
    else:
        A[i]=a
        D[a]=1

if s==N:
    ans=sum(A[:i])
else:
    A=A[:i]
    
    ans=0
    l=len(A)-s
    ans+=sum(A[:s])
    S=sum(A[s:])
    T=(N-s)//l
    ans+=T*S
    K=N-s-l*T
    ans+=sum(A[s:(s+K)])


print(ans)


# -*- coding: utf-8 -*-

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

A=[0]*(M+1)
A[0]=X
D=[0]*(M+1)

s=N
for i in range(1,N):
    a=A[i-1]**2%M
    if D[a] == 1:
        s=A.index(a)
        break
    else:
        A[i]=a
        D[a]=1

if s==N:
    ans=sum(A)
else:
    A=A[:i]
    
    ans=0
    l=len(A)-s
    ans+=sum(A[:s])
    S=sum(A[s:])
    T=(N-s)//l
    ans+=T*S
    K=N-s-l*T
    ans+=sum(A[s:(s+K)])


print(ans)


Verdicts: Runtime Error

Accepted
Problem: 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}.

Submission attempts (in order):
N,X,M = map(int,input().split())

d = {X:0}
l = [X]
s = 0

for i in range(1,N):
  l+=[(l[i-1]**2)%M]
  if l[i] in d:
    dl = l[d[l[i]]+1:]
    s += sum(dl)*((N-i-1)//len(dl))
    if (N-i-1)%len(dl) != 0:
      s += sum(dl[0:(N-i-1)%len(dl)])
    break
  s += l[i]
  d[l[i]] = i
print(s)

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

d = {X:0}
l = [X]

for i in range(1,N):
  l+=[(l[i-1]**2)%M]
  if l[i] in d:
    dl = l[d[l[i]]+1:]
    print(dl)
    l += dl*((N-i-1)//len(dl))
    if (N-i-1)%len(dl) != 0:
      l += dl[0:(N-i-1)%len(dl)]
    break
  d[l[i]] = i
print(l)
print(sum(l))

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

d = {X:0}
l = [X]
s = X

for i in range(1,N):
  l+=[(l[i-1]**2)%M]
  s += l[i]
  if l[i] in d:
    dl = l[d[l[i]]+1:]
    s += sum(dl)*((N-i-1)//len(dl))
    if (N-i-1)%len(dl) != 0:
      s += sum(dl[0:(N-i-1)%len(dl)])
    break
  d[l[i]] = i
print(s)

Verdicts: Wrong Answer

Runtime Error

Accepted
Problem: 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}.

Submission attempts (in order):
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

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

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)

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)

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

Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Accepted
Problem: 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}.

Submission attempts (in order):
n,x,m = map(int,input().split())
mod = m
ans = 0
bit = [-1 for i in range(m)]
cycle = False
for i in range(n):
    if i == 0 :
        a = x
        bit[a] = i
        ans += a
    else:
        a = (a**2)% mod
        if bit[a] != -1:
            cy_st = bit[a]
            cy_fi = i -1
            cycle = True
            break
        else:
            bit[a] = i
            ans += a

if cycle:
    ans2 = x
    a = x
    for j in range(1,cy_st):
        a = (a**2)% mod
        ans2 += a
    cy_num = ans - ans2
    cy_repe = (n-cy_st) // (cy_fi - cy_st + 1)
    ans3 = cy_num * cy_repe
    cy_amari = (n-cy_st) % (cy_fi - cy_st + 1)
    for i in range(cy_amari):
        a = (a**2)% mod
        ans3 += a

print(ans2+ans3)


n,x,m = map(int,input().split())
mod = m
ans = 0
bit = [-1 for i in range(m)]
cycle = False
for i in range(n):
    if i == 0 :
        a = x
        bit[a] = i
        ans += a
    else:
        a = (a**2)% mod
        if bit[a] != -1:
            cy_st = bit[a]
            cy_fi = i -1
            cycle = True
            break
        else:
            bit[a] = i
            ans += a

if cycle:
    ans2 = 0
    b =  -1
    for j in range(cy_st):
        if j == 0 :
            b = x
            ans2 += b
        else:
            b = (b**2)% mod
            ans2 += b
    cy_num = ans - ans2
    cy_repe = (n-cy_st) // (cy_fi - cy_st + 1)
    ans3 = cy_num * cy_repe
    cy_amari = (n-cy_st) % (cy_fi - cy_st + 1)
    
    if b == -1:
        for j in range(cy_amari):
            if j == 0 :
                b = x
                ans3 += b
            else:
                b = (b**2)% mod
                ans3 += b
        
    else:
        for i in range(cy_amari):
            b = (b**2)% mod
            ans3 += b

    print(ans2+ans3)
else:
    print(ans)


Verdicts: Runtime Error

Accepted
Problem: 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}.

Submission attempts (in order):
import numpy as np
i8 = np.int64


def solve(N, X, M):
    memo_val = np.zeros(M, i8)
    memo_i = np.zeros(M, i8)
    ret = 0
    a = X
    for i in range(1, N):
        ret += a
        if memo_i[a] > 0:
            u = (N - memo_i[a]) // (i - memo_i[a])
            v = (N - memo_i[a]) % (i - memo_i[a])
            ret = u * (ret - memo_val[a])
            nokori = v + memo_i[a]
            for j in range(M):
                if memo_i[j] == nokori:
                    ret += memo_val[j]
            return ret
        memo_i[a] = i
        memo_val[a] = ret
        a = a ** 2 % M
    return ret


N, X, M = [int(x) for x in input().split()]
ans = solve(N, X, M)
print(ans)

import numpy as np
i8 = np.int64


def solve(N, X, M):
    memo_val = np.zeros(M, i8)
    memo_i = np.zeros(M, i8)
    ret = 0
    a = X
    for i in range(1, N):
        ret += a
        if memo_i[a] > 0:
            u = (N - memo_i[a]) // (i - memo_i[a])
            v = (N - memo_i[a]) % (i - memo_i[a])
            ret = u * (ret - memo_val[a])
            nokori = v + memo_i[a]
            for j in range(M):
                if memo_i[j] == nokori:
                    ret += memo_val[j]
            return ret
        memo_i[a] = i
        memo_val[a] = ret
        a = a ** 2 % M
    ret += a
    return ret

def main():
    f = open(0)
    N, X, M = [int(x) for x in f.readline().split()]
    ans = solve(N, X, M)
    print(ans)

main()

Verdicts: Wrong Answer

Accepted
Problem: 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}.

Submission attempts (in order):
N,X,M=map(int,input().split())
A = [X,]
setA = {A,}
alast=X
flag=False
for i in range(min(N-1,M)):
    P=alast**2%M
    if P in setA:
        flag=True
        d = A.index(P)
        C=A[d:]
        alast=P
        break
    else:
        A.append(P)
        setA.add(P)
        alast=P
if alast==0:
    print(sum(C))
elif (flag==False) and (alast!=0):
    print(sum(A))
else:
    suma=sum(C)
    res = (N-d)%len(C)
    print(sum(A[:d])+((N-d)//len(C))*suma + sum(C[:res]))

N,X,M=map(int,input().split())
A = [X,]
setA = {X,}
alast=X
flag=False
for i in range(min(N-1,M)):
    P=alast**2%M
    if P in setA:
        flag=True
        d = A.index(P)
        C=A[d:]
        alast=P
        break
    else:
        A.append(P)
        setA.add(P)
        alast=P
if flag:
    if alast==0:
        ans = sum(A)
    else:
        res = (N-d)%len(C)
        ans = sum(A[:d])+((N-d)//len(C))*sum(C) + sum(C[:res])
else:
    ans = sum(A) 
print(ans)

Verdicts: Runtime Error

Accepted
Problem: 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}.

Submission attempts (in order):
 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)))

N, X, M = map(int, input().split())
NN = N
li = []
isused = [False] * M
while isused[X] == False and N != 0:
    li.append(X)
    isused[X] = True
    X = (X ** 2) % M
    N -= 1
    
if N == 0:
    print(sum(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) + sum(li[i] for i in range(s, len(li))) * (q-1) + sum(li[i] for i in range(s, s + r)))

Verdicts: Runtime Error

Accepted
Problem: 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}.

Submission attempts (in order):
n,x,m = map(int, input().split()) 
ans = 0
x_list = []

for i in range(m):
    if i == n or x == 0:
        ans = sum(x_list)
        print(ans)
        exit()
    x_list.append(x)
    x = (x**2)%m
    
    if x_list.count(x) == 1:
        break

for i in range(len(x_list)):
    if x_list[i] == x:
        roop = list(x_list[i:])
        if n % len(roop) == 0:
            ans = sum(roop)*(n//len(roop) - 1) + sum(x_list)
            print(ans)
        else:
            ans = sum(roop)*(n//len(roop) - 1) + sum(x_list) + sum(roop[:(n//len(roop))])
            print(ans)
        exit()

N,x,M=map(int,input().split())
k=x
L=list()
c=dict()
for i in range(M):
  if i==N:
    print(sum(L))
    exit()
  if x==0:
    print(sum(L))
    exit()
  L.append(x)
  x=(x*x)%M
  if x in c:
    q=x
    break
  c[x]=1
moto=sum(L)
N-=len(L)
for i in range(len(L)):
  if L[i]==q:
    roop=list(L[i:])
L=roop
a=len(L)
if N%a==0:
  print(moto+(sum(L)*(N//a)))
else:
  s=N//a
  t=N%a
  ans=sum(L)*s
  ans+=sum(roop[:t])
  print(moto+ans)

Verdicts: Wrong Answer

Accepted
Problem: 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}.

Submission attempts (in order):
n,x,m=map(int,input().split())
cnt2=set()
cnt2.add(x)
cnt3=[x]
cnt4=0
cnt5=0
cnt6=x
for i in range(1,m+10):
    num2=pow(cnt6,2,m)
    if num2 in cnt2:
        for j in range(len(cnt3)):
            if cnt3[j]==num2:
                cnt7=j
                break
        cnt10=len(cnt3)-cnt7
        num4=sum(cnt3[:cnt7])
        cnt4=len(cnt3)
        break
    cnt2.add(num2)
    cnt3.append(num2)
    cnt6=num2
    if num2==0:
        ans=sum(cnt3)
        cnt5=1
        break
if cnt5==0:
    ans=num4
    n-=cnt7
    ans+=(n//cnt10)*sum(cnt3[cnt7:])
    ans+=sum(cnt3[cnt7:(n%cnt10)+cnt7])
if cnt4>=n:
    ans=sum(cnt3[:n])
print(ans)


n,x,m=map(int,input().split())
cnt2=set()
cnt2.add(x)
cnt3=[x]
cnt4=0
cnt5=0
cnt6=x
for i in range(1,m+10):
    num2=pow(cnt6,2,m)
    if num2 in cnt2:
        for j in range(len(cnt3)):
            if cnt3[j]==num2:
                cnt7=j
                break
        cnt10=len(cnt3)-cnt7
        num4=sum(cnt3[:cnt7])
        cnt4=len(cnt3)
        break
    cnt2.add(num2)
    cnt3.append(num2)
    cnt6=num2
    if num2==0:
        ans=sum(cnt3)
        cnt5=1
        break
if cnt5==0 and n>cnt4:
    ans=num4
    n-=cnt7
    ans+=(n//cnt10)*sum(cnt3[cnt7:])
    ans+=sum(cnt3[cnt7:(n%cnt10)+cnt7])
if cnt4>=n:
    ans=sum(cnt3[:n])
print(ans)


Verdicts: Wrong Answer

Accepted
Problem: 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}.

Submission attempts (in order):
n,x,m=map(int,input().split())
ans=0
p=0
l=[x]
if x%m==0:
  print(x)
else:
  for i in range(1,n):
    s=(l[i-1]**2)%m
    if s==0:
      p=1
      break
    if s in l:
      break
    else:
      l.append(s)
  if p==0:
    t=sum(l[1:])
    k=n//(len(l)-1)
    j=n%(len(1)-1)
    ans=x+t*k+sum(l[1:j+1])
    print(ans)
  else:
    print(sum(l))

n,x,m=map(int,input().split())
order=[-1 for i in range(m)] 
index=0 
a=[] 
while order[x]==-1: 
  order[x]=index 
  a.append(x)
  x=(x**2)%m
  index+=1
tmp=sum(a[order[x]:index]) 
t=index-order[x] 
if n-1<order[x]: 
  print(sum(a[:n]))
else:
  sum1=sum(a[:order[x]]) 
  x1=n-order[x] 
  n1=x1//t 
  n2=x1%t
  print(sum1+n1*tmp+sum(a[order[x]:order[x]+n2]))

Verdicts: Runtime Error

Accepted
Problem: 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}.

Submission attempts (in order):
# -*- coding: utf-8 -*-

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




def f(x: int, m: int) -> int:
    return x**2 % m


A = {X}
loop_start_index = 0
while True:
    A_next = f(A[-1], M)
    if A_next in A:
        loop_start_index = A.index(A_next)
        break
    else:
        A.add(A_next)

loop_length = len(A) - loop_start_index
loop_cnt = (N - loop_start_index) // loop_length
loop_res = (N - loop_start_index) % loop_length
ans = sum(A[:loop_start_index]) + \
    loop_cnt * sum(A[loop_start_index:]) + \
    sum(A[loop_start_index: loop_start_index + loop_res])


print(ans)


# -*- coding: utf-8 -*-

def get_input() -> tuple:
    
    
    N, X, M = list(map(int, input().split()))

    return N, X, M


def f(x: int, m: int) -> int:
    
    return x % m


def main(N: int, X: int, M: int) -> None:
    
    
    A = [X]
    s = {X}
    i = 0
    while True:
        A_next = f(A[-1], M)
        if A_next in s:
            i = A.index(A_next)
            break
        else:
            A.append(A_next)
            s.add(A_next)

    loop_length = len(A) - i
    loop_cnt = (N - i) // loop_length
    loop_res = (N - i) % loop_length
    ans = sum(A[:i]) + loop_cnt * sum(A[i:]) + sum(A[i: i + loop_res])

    
    print(ans)


if __name__ == "__main__":
    
    N, X, M = get_input()

    
    main(N, X, M)


# -*- coding: utf-8 -*-

def get_input() -> tuple:
    
    
    N, X, M = list(map(int, input().split()))

    return N, X, M


def f(x: int, m: int) -> int:
    
    return x % m


def main(N: int, X: int, M: int) -> None:
    
    
    A = [X]
    s = {X}
    i = 0
    while True:
        A_next = f(A[-1]**2, M)
        if A_next in s:
            i = A.index(A_next)
            break
        else:
            A.append(A_next)
            s.add(A_next)

    loop_length = len(A) - i
    loop_cnt = (N - i) // loop_length
    loop_res = (N - i) % loop_length
    ans = sum(A[:i]) + loop_cnt * sum(A[i:]) + sum(A[i: i + loop_res])

    
    print(ans)


if __name__ == "__main__":
    
    N, X, M = get_input()

    
    main(N, X, M)


Verdicts: Runtime Error

Wrong Answer

Accepted
Problem: 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}.

Submission attempts (in order):
import sys, math, re
from functools import lru_cache
from collections import deque
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N, X, M = mi()
    r = [-1]*M

    now = X
    cnt = 0
    while True:
        if r[now] != -1:
            break
        r[now] = cnt
        now = (now*now)%M
        cnt += 1

    d = [(r[i], i) for i in range(M) if r[i] != -1]
    d.sort()
    T = len(d)-r[now]

    s = list(v for k, v in d if k < len(d)-T)
    t = list(v for k, v in d if k >= len(d)-T)

    if N < len(s):
        ans = sum(s[:N])
    else:
        ans = sum(s) + sum(t)*((N-len(s))//M) + sum(t[:(N-len(s))%M])
        print(sum(s), sum(t)*((N-len(s))//M), sum(t[:(N-len(s))%M]))

    print(ans)



if __name__ == "__main__":
    main()

import sys, math, re
from functools import lru_cache
from collections import deque
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N, X, M = mi()
    r = [-1]*M

    now = X
    cnt = 0
    while True:
        if r[now] != -1:
            break
            
        r[now] = cnt

        now = (now*now)%M
        cnt += 1
    
    d = [(r[i], i) for i in range(M) if r[i] != -1]
    d.sort()

    s = [v for k, v in d[:r[now]]]
    t = [v for k, v in d[r[now]:]]

    ns = len(s)
    nt = len(t)

    if N < ns:
        print(sum(s[:N]))
        return
    
    print(sum(s) + sum(t) * ((N-ns)//nt) + sum(t[:(N-ns)%nt]))



if __name__ == "__main__":
    main()

Verdicts: Wrong Answer

Accepted
Problem: 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}.

Submission attempts (in order):
N, X, M = map(int, input().split())
flag = [False for _ in range(M)]
record = list()
record.append(X)
flag[X] = 1

An = X

for i in range(M + 1):
    An = pow(An, 2, M)
    if flag[An]:
        start = flag[An]
        cnt = i + 2 - start
        cost = record[-1] - record[start - 2] if start > 1 else record[-1]
        break

    else:
        record.append(An + record[-1])
        flag[An] = i + 2

if start >= N:
    print(record[N - 1])
else:
    print(((N - start) // cnt) * cost
                + record[(N - start) % cnt + start - 1])
    print(cost)


N, X, M = map(int, input().split())
record_sum = [0, ]
flag = [False for _ in range(M)]
An = X

# n=1
record_sum.append(An)
flag[An] = 1

for i in range(2, M + 2):
    An = pow(An, 2, M)  
    record_sum.append(record_sum[-1] + An)

    if flag[An]:
        start_index = flag[An]
        initial_cost = record_sum[start_index - 1]
        cycle_cost = record_sum[-1] - record_sum[start_index]
        cycle_length = i - start_index
    else:
        flag[An] = i

if start_index >= N:
    print(record_sum[N])

else:
    ans = 0
    ans += ((N - start_index) // cycle_length) * cycle_cost
    ans += record_sum[(N - start_index) % cycle_length + start_index]

    print(ans)


Verdicts: Wrong Answer

Accepted