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

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(m):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    if icntk==0:
#        print("0:",ai,asum,icnt,ai0,asum0,icnt0)
        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
        ans=x*n
        print(ans)       
    else:
#        print("1:",ai,asum,icnt,ai0,asum0,icnt0)
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
        ans=asum0+asumk*nk+asumr    
        print(ans)

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
if X <= 1:
    print(X*N)
    exit()
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:
    print(N*X)
    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: Wrong Answer

Solution code:

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

if x==0:
    print(0)
if x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(m):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    if icntk==0:
#        print("0:",ai,asum,icnt,ai0,asum0,icnt0)
        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
        ans=x*n
        print(ans)       
    else:
#        print("1:",ai,asum,icnt,ai0,asum0,icnt0)
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
        ans=asum0+asumk*nk+asumr    
        print(ans)

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
if X <= 1:
    print(X*N)
    exit()
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:
    print(N*X)
    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: Wrong Answer

Solution code:

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

if x==0:
    print(0)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(m):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    if icntk==0:
#        print("0:",ai,asum,icnt,ai0,asum0,icnt0)
        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
        ans=x*n
        print(ans)       
    else:
#        print("1:",ai,asum,icnt,ai0,asum0,icnt0)
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
        ans=asum0+asumk*nk+asumr    
        print(ans)

Submission status: Wrong Answer

Solution code:
N, X, M = map(int, input().split())
if X <= 1:
    print(X*N)
    exit()
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:
    pass

ans = X
A = X
for i in range(min(N,first_count)-1):
    A = (A**2)%M
    ans += A
if N > first_count and roop_count != 0:
    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: Wrong Answer

Solution code:

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

if x==0:
    print(0)
elif m==1:
    print(0)
elif n<=m*3:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(m):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    if icntk==0:
        icntk=1
        n0=n-1-icnt0
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
    else:
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Submission status: Wrong Answer

Solution code:

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

if x==0:
    print(0)
elif m==1:
    print(0)
elif n<=m*3:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(m):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    if icntk==0:
        icntk=1
        n0=n
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
    else:
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Submission status: Wrong Answer

Solution code:

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

if x==0:
    print(0)
elif m==1:
    print(0)
elif n<=m*3:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(m):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    if icntk==0:
        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
    else:
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
r=[]
s=set()
ans=x
a=x
for i in range(n-1):
    b=a*a%m
    if b in s:
        j = r.index(b)
        N = n-j
        T = i-j
        S = sum(r[j:i])
        ans += N//T*S
        N %= T
        ans += sum(r[j:j+N])
        break
    else:
        ans+=b
        s.add(b)
        r.append(b)
        a=b
print(ans)

Submission status: Wrong Answer

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

a = []
check = [-1] * m
i = 0
while check[x] == -1:
  a.append(x)
  check[x] = i
  x = x * x % m
  i += 1
if n <= i:
  print(sum(a[:n]))
else:
  print(
    sum(a[:check[x]])
    + (n - check[x]) // (i - check[x]) * sum(a[check[x]:])
    + sum(a[check[x] : check[x] + (n - check[x]) // (i - check[x])]))

Submission status: Wrong Answer

Solution code:
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)

Submission status: Wrong Answer

Solution code:

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

if x==0:
    print(0)
elif m==1:
    print(0)
elif n<=m*3:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(m):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    if icntk==0:
        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=asum
        asumr=0
    else:
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Submission status: Wrong Answer

Solution code:

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

if x==0:
    print(0)
elif m==1:
    print(0)
elif n<=m*3:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(m):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    if icntk==0:
        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=asum
    else:
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
    asumr=0
    air=ai
    for i in range(nr):
        asumr+=air
        air=(air*air)%m
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Submission status: Wrong Answer

Solution code:
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]
        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])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

# https://en.wikipedia.org/wiki/Cycle_detection
def floyd_cycle_finding(f, x0):
    '''
    循環していない部分の長さをlam
    循環部分の長さをmuとして
    (lam, mu)
    を返す
    >>> floyd_cycle_finding(lambda x: x**2 % 3, 2)
    (1, 1)
    >>> floyd_cycle_finding(lambda x: x**2 % 1001, 2)
    (2, 4)
    >>> floyd_cycle_finding(lambda x: x**2 % 16, 2)
    (2, 1)
    >>> floyd_cycle_finding(lambda x: x*2 % 5, 3)
    (0, 4)
    >>> floyd_cycle_finding(lambda x: x*2 % 5, 0)
    (0, 1)
    '''
    # a_i = a_j
    # の関係が成り立つ時
    # a_{lam+n+k*mu} = a_{lam+n+k'*mu}
    # より|i-j|は循環の長さの整数倍になる
    # そこで
    # a_m = a_2m
    # なるmを見つける
    # 前述の性質からmは循環の長さの整数倍となっているため
    # 2m - m = m = k*mu = lam + n + k'*mu
    # したがって、lam + nはmuの倍数となるので
    # 地点mからlamステップ進むと循環の開始点に到達する
    # lamが求まれば後は流れでmuも求まる
    
    tortoise = f(x0)
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
    lam = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        lam += 1
    mu = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        mu += 1
    return lam, mu

def solve(N: int, X: int, M: int):
    f = lambda x: x**2 % M

    def g(x):
        while True:
            yield x
            x = f(x)
            
    lam, mu = floyd_cycle_finding(f, X)
    ans = 0
    gg = g(X)
    k = max((N - lam) // mu, 0)
    for i in range(min(N, lam)):
        ans += next(gg)
    for i in range(min(N-lam, mu)):
        ans += k * next(gg)
    for i in range((N-lam)%mu):
        ans += next(gg)
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    print(solve(N, X, M))


def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    test()
    main()

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
ida = [-1] * (m + 1)
a = [-1] * (m + 1)
sa = [-1] * (m + 1)
a[1] = x
sa[1] = x
ida[x] = 1
l_len = 1
l_start = 1
for i in range(2, m + 1):
    fx = a[i - 1] ** 2 % m
    if ida[fx] < 0:
        ida[fx] = i
        a[i] = fx
        sa[i] = sa[i - 1] + a[i]
    else:
        a[i] = fx
        l_start = a.index(fx)
        l_len = i - l_start
        break
q = (n - l_start + 1) // l_len
r = (n - l_start + 1) % l_len
if n == 1:
    ans = x
else:
    ans = (sa[l_start + l_len - 1] - sa[l_start - 1]) * q + sa[l_start + r - 1]
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

# https://en.wikipedia.org/wiki/Cycle_detection
def floyd_cycle_finding(f, x0):
    '''
    循環していない部分の長さをlam
    循環部分の長さをmuとして
    (lam, mu)
    を返す
    >>> floyd_cycle_finding(lambda x: x**2 % 3, 2)
    (1, 1)
    >>> floyd_cycle_finding(lambda x: x**2 % 1001, 2)
    (2, 4)
    >>> floyd_cycle_finding(lambda x: x**2 % 16, 2)
    (2, 1)
    '''    
    tortoise = f(x0)
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
    lam = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        lam += 1
    mu = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        mu += 1
    return lam, mu

def solve(N: int, X: int, M: int):
    f = lambda x: x**2 % M

    def g(x):
        while True:
            yield x
            x = f(x)
            
    lam, mu = floyd_cycle_finding(f, X)
    ans = 0
    gg = g(X)
    k = (N - lam) // mu
    for i in range(min(N, lam)):
        ans += next(gg)
    for i in range(min(N-lam, mu)):
        ans += k * next(gg)
    for i in range((N-lam)%mu):
        ans += next(gg)
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    print(solve(N, X, M))


def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    test()
    main()

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
ida = [-1] * (m+1)
a = [-1] * (m + 1)
sa = [-1] * (m + 1)
a[1] = x
sa[1] = x
ida[x] = 1
l_len = 1
l_start = 1
for i in range(2, m + 1):
    fx = a[i - 1] ** 2 % m
    if ida[fx] < 0:
        ida[fx] = i
        a[i] = fx
        sa[i] = sa[i - 1] + a[i]
    else:
        a[i] = fx
        l_start = a.index(fx)
        l_len = i - l_start
        break

q = (n-l_start+1) // l_len
r = (n-l_start+1) % l_len

ans = (sa[l_start + l_len - 1] - sa[l_start-1])*q +sa[l_start+r-1]
print(ans)

Submission status: Wrong Answer

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])
        print(np.sum(l[:loop_start]) + np.sum(l[loop_start:])*((n-loop_start)//(i-loop_start+1))+np.sum(l[loop_start:loop_start+(n-loop_start)%(i-loop_start+1)]))
        print("i")
        sys.exit()
    else:
        l = np.append(l,ans)
print(np.sum(l))

Submission status: Wrong Answer

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-2)//(i-b+1))+np.sum(l[b:b+(n-2)%(i-b+1)]))
        sys.exit()
    else:
        l = np.append(l,ans)
print(np.sum(l))

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
fxid = [-1] * (m)
a = [0] * (m + 1)
sa = [0] * (m + 1)
a[1] = x
sa[1] = x
fxid[x] = 1
l_len = 1
l_start = 1
for i in range(2, m + 1):
    fx = a[i - 1] ** 2 % m
    if fxid[fx] < 0:
        fxid[fx] = i
        a[i] = fx
        sa[i] = sa[i - 1] + a[i]
    else:
        a[i] = fx
        l_start = a.index(fx)
        l_len = i - l_start
        break

ans1 = sa[l_start - 1]
ans2 = sa[l_start + l_len - 1] - sa[l_start - 1]
ans3 = sa[(l_start - 1+n - l_start+1) % l_len] - sa[l_start - 1]
ans = ans1 + ans2 + ans3

print(ans)

Submission status: Wrong Answer

Solution code:
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:
        b = x
        ans3 += b
    for i in range(1,cy_amari):
        b = (b**2)% mod
        ans3 += b

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

Submission status: Wrong Answer

Solution code:
N,X,M=map(int,input().split())
a=[0]*(M)
A=X%M
a[A]=1
ans=A
Ans=[A]
flag=0
for i in range(N):
    A=A*A%M
    if A==0:
        break
    if a[A]==1:
        flag=1
        break
    a[A]=1
    ans+=A
    Ans.append(A)
if flag==1:
    for num in range(len(Ans)):
        if A==Ans[num]:
            break
    n=len(Ans)-num
    b=sum(Ans[:num])
    x=N//n
    y=N%n
    Sum=(ans-b)*(x)+sum(Ans[:y])
else:
    Sum=sum(Ans)
print(Sum)

Submission status: Wrong Answer

Solution code:
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
    for j in range(cy_st):
        if j == 0 :
            a = x
            ans2 += a
        else:
            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)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
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)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int,input().split())
a = x; s = a
k = {a}
memo = [a]
mode = 0
cnt = 1
for i in range(n):
	a = (a**2)%m
	cnt += 1
	memo.append(a)
	if a in k:
		mode = 1
		break
	s += a
	k.add(a)
if mode:
	targ = memo.index(a)
	nagasa = cnt-1-targ
	ruisekiwa = [0 for _ in range(nagasa)]
	ruisekiwa[0] = memo[targ]
	for i in range(1, nagasa):
		ruisekiwa[i] = ruisekiwa[i-1] + memo[i+targ]
	t = n - cnt
	s += ruisekiwa[-1]*(t//nagasa) + ruisekiwa[t%nagasa]
print(s)

Submission status: Wrong Answer

Solution code:
import math

N,X,M = map(int, input().split())
MAP = [-1]*(M+1)
TMAP = [0]*(M+1)
ans = 0

for i in range(N):
    if (X%M!=0):
        X = X%M
        ans += X
        if MAP[X]==-1:
            MAP[X] = i
            TMAP[X] = ans
        else:
            loopcnt = i-MAP[X]
            loopsum = ans-TMAP[X] #怪しい
            ans += (((N-MAP[X])//loopcnt)-1)*loopsum
            jmax = N-(MAP[X]+((N-MAP[X])//loopcnt)*loopcnt)
            for j in range(jmax):
                X = X%M
                ans += X
                X = X**2
            X=M
        X = X**2
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
sm=[-1 for i in range(m)]
w=[-1 for i in range(m)]
d=[]
a=x
t=0
s=0
while True:
  s+=a
  if w[a]!=-1:
    inter=t-w[a]
    fv=w[a]
    ls=d[(n-fv)%inter+fv-1]
    lls=d[w[a]-1]
    print(sm[lls]+(n-fv)//inter*(s-sm[a])+(sm[ls]-sm[lls]))
    break
  w[a]=t
  d.append(a)
  sm[a]=s
  t+=1
  a=(a*a)%m

Submission status: Wrong Answer

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 #ループ開始の最初の配列のの番号
        break
else:
    stnum = len(num) - 1


if 0 in num:
    ans = sum(num[:n])
else:
    if (len(num)-stnum) != 0:
        rest = (n-stnum)%(len(num)-stnum) #余り
        qu = (n-stnum)//(len(num)-stnum)  #商
    else:
        rest = n
        qu = 0
        ans = sum(num[:stnum]) + sum(num[stnum:stnum+rest]) + sum(num[stnum:])*qu
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

class loop:
    def __init__(self, x):
        self.sequence = []
        self.accumseq = []
        self.start = None
        self.loop = None
        self.loopsum = None
        self.x = x
        self.get_loop()

    def next(self, x):
        return f(x)

    def get_loop(self):
        s = set([self.x])
        self.sequence.append(self.x)
        self.accumseq.append(self.x)
        nxt = self.next(self.x)
        while not nxt in s:
            s.add(nxt)
            self.sequence.append(nxt)
            self.accumseq.append(self.accumseq[-1] + nxt)
            nxt = self.next(nxt)
        self.start = self.sequence.index(nxt)
        self.loop = len(self.sequence) - self.start
        self.loopsum = self.accumseq[-1] - self.accumseq[self.start-1]

    def revise_n(self, n):
        lp = self.loop
        lpt = (n-(self.start + lp)+(lp-1))//lp
        nn = n - lpt * self.loop
        return [nn, lpt]

    def get_nth_elment(self, n):
        n , _ = self.revise_n(n)
        return self.sequence[n]

    def get_nth_sum(self, n):
        n , lpt = self.revise_n(n)
        return self.accumseq[n-1] + lpt * self.loopsum

####################

n, x, m = map(int, input().split())
def f(x):
    return pow(x, 2, m)

clslp = loop(x)
ret = clslp.get_nth_sum(n)
print(ret)

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
# -1はまだ来てない
order=[-1 for i in range(m)]
index=0
#0,1,2,...　番目の数字を配列で記憶高々mこ
a=[]
while(order[x]==-1):
    order[x]=index
    a.append(x)
    x=(x**2)%m
    index+=1
#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]])
    print(sum1)
    #ループ前を全体から引いた数
    x1=n-order[x]
    print(x1)
    #ループ回数
    n1=x1//T
    n2=x1%T
    print(sum1+n1*tmp+sum(a[order[x]:order[x]+n2]))

Submission status: Wrong Answer

Solution code:
n,x,m=map(int,input().split())
a=x
w=x
for i in range(0,n-1):
  p=(a*a)%m
  print(p)
  w=w+p
  a=p
print(w)

Submission status: Wrong Answer

Solution code:
import sys
from sys import stdin
def I():
    return stdin.readline().rstrip()
def MI():
    return map(int,stdin.readline().rstrip().split())
def LI():
    return list(map(int,stdin.readline().rstrip().split()))
#main part
n,x,m=MI()
stock=[]
for _ in range(1,n+1):
    if x not in stock:
        stock.append(x)
        x=(x**2)%m
    else:
        start=stock.index(x)
        repeat=stock[start:]
        l=len(repeat)
        n-=start
        sho=n//l
        amari=n%l
        s=sum(repeat)
        rest=0
        if amari!=0:
            for j in range(amari):
                rest+=repeat[j]
        print(s*sho+amari+sum(stock[:start]))
        sys.exit()
print(sum(stock))

Submission status: Wrong Answer

Solution code:
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)

Submission status: Wrong Answer

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

num=i-t[x]+1
re=s[i]-s[t[x]-1]
sho=s[t[x]-1]
ans=sho+re*((n-t[x]+1)//num)+(s[t[x]-1+((n-2)%num)]-s[t[x]-1])
print(ans)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
s = x
a = x
note = [0] * m
note[a] += 1
seq = []
for i in range(n-1):
    seq.append(a)
    a = a**2 % m
    if note[a] > 0:
        ind = seq.index(a)
        l = len(seq[ind:])
        n -= len(seq[:ind-1])
        syo, r = divmod(n, l)
        s = s + sum(seq[ind:]) * (syo-1)
        if r != 0:
            for j in range(ind, ind+r-1):
                s += seq[j]
        print(s)
        exit()
    if a == 0:
        print(s)
        exit()
    note[a] += 1
    s += a
print(s)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
s = x
a = x
note = [0] * m
note[a] += 1
seq = []
for i in range(n-1):
    seq.append(a)
    a = a**2 % m
    if note[a] > 0:
        ind = seq.index(a)
        l = len(seq[ind:])
        n -= len(seq[:ind-1])
        syo, r = divmod(n, l)
        s = s + sum(seq[ind:]) * (syo-1)
        print(s)
        exit()
    if a == 0:
        print(s)
        exit()
    note[a] += 1
    s += a
print(s)

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
s = x
a = x
note = [0] * m
note[a] += 1
seq = []
for i in range(n-1):
    seq.append(a)
    a = a**2 % m
    if note[a] > 0:
        ind = seq.index(a)
        l = len(seq[ind:])
        if ind != 0:
            n -= len(seq[:ind-1])
        syo = n // l
        r = n % l
        s = s + sum(seq[ind:]) * (syo-1)
        if r != 0:
            for j in range(ind, ind+r-1):
                s += seq[j]
        print(s)
        exit()
    if a == 0:
        print(s)
        exit()
    note[a] += 1
    s += a
print(s)

Submission status: Wrong Answer

Solution code:
import numpy as np
from sys import stdin
import copy

def main():
    input = stdin.readline
    n, x, m = map(int, input().split())
    a = np.array([x], dtype=np.int64)
    h = {}
    h[x] = 0
    t = 0
    for i in range(n - 1):
        t = a[i] * a[i] % m
        if t in h:
            break
        h[t] = 0
        a = np.append(a, t)
    b = copy.deepcopy(a)
    if bool(np.where(a == t)[0]):
        a = a[:np.where(a == t)[0][0]]
    b = np.setdiff1d(b, a)
    ans = np.sum(a, dtype=np.int64)
    if len(b) > 0:
        ans += np.sum(b, dtype=np.int64) * ((n - len(a)) // len(b))
        ans += np.sum(b[0: (n - len(a)) % len(b)], dtype=np.int64)
    print(ans)
main()