Problem:


Score : 600 points

Problem Statement

Given is an integer N.
Find the minimum possible positive integer k such that (1+2+\cdots+k) is a multiple of N.
It can be proved that such a positive integer k always exists.

Constraints

1 \leq N \leq 10^{15}

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer in a line.

Sample Input 1

11

Sample Output 1

10

1+2+\cdots+10=55 holds and 55 is indeed a multple of N=11.
There are no positive integers k \leq 9 that satisfy the condition, so the answer is k = 10.

Sample Input 2

20200920

Sample Output 2

1100144



Sample input:
11


Sample output:
10

Submission status: Accepted

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

n = int(input()) * 2
D = []

for i in range(2, int(n**0.5) + 1):
    d = 1
    while n%i == 0:
        n //= i
        d *= i
    if d != 1:
        D.append(d)
    if n == 1:
        break
if n != 1:
    D.append(n)
# print(D)

# 拡張Euclidの互除法。ap + bq = gcd(a, b) となる p, q, d=gcd(a, b) を返す。
def extgcd(a, b):
    if b == 0:
        return 1, 0, a
    q, p, d = extgcd(b, a%b)
    q -= (a // b) * p
    return p, q, d

def crt(R, M):  # 中国剰余定理。Rは余り、Mは割る数の配列。不定なら(0,1)、不能なら(0,0)が返る。
    r = 0
    m = 1
    for i in range(len(R)):
        p, _, d = extgcd(m, M[i])
        if (R[i] - r) % d != 0:
            return (0, 0)
        tmp = (R[i] - r) // d * p % (M[i] // d)
        r += m * tmp
        m *= M[i] // d
    return (r % m, m)


ans = float("inf")

# Rs = []

for i in range(1, 2**len(D)):
    ib = format(i, "b").zfill(len(D))
    R = [0] * len(D)
    for j in range(len(D)):
        if ib[j] == "1":
            R[j] = D[j]-1
    ans = min(ans, crt(R, D)[0])
print(ans)

Submission status: Accepted

Solution code:
def divisor(n):
    ret = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ret.append(i)
            if i*i != n:
                ret.append(n//i)
    return ret
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
def extgcd(a, b):
    x0, x1, y0, y1 = 0,1,1,0
    while a:
        g,b,a = b//a, a, b%a
        y0,y1 = y1, y0-g*y1
        x0,x1 = x1, x0-g*x1
    return x0, y0, b

def get_t(A,y):
    ta = int(-A/y) + 1
    if -A < 0 and A%y != 0:
        ta = int(-A/y)
    return ta

n = int(input())
if n == 2:
    k = 3
elif is_prime(n):
    k = n-1
else:
    k = float("inf")
    n = 2*n
    div = divisor(n)
    for x in div:
        y = n//x
        A, B, g = extgcd(x, -y)
        if g == 1:
            ta = get_t(A, y)
            tb = get_t(B, y)
            t = max(ta, tb)
            a = A + y*t
            b = B + x*t
            ax = a*x
            by = b*y
            k = min(k, by)

print(k)

Submission status: Accepted

Solution code:
def prime_factor(n):
    factors = {}
    if n % 2 == 0:
        cnt = 0
        while n % 2 == 0:
            cnt += 1
            n //= 2
        factors[2] = cnt
    i = 3
    while i * i <= n:
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            factors[i] = cnt
        i += 2
    if n != 1:
        factors[n] = 1
    return factors

def extgcd(a, b):
    s, sx, sy, t, tx, ty = a, 1, 0, b, 0, 1
    while t:
        q = s // t
        s -= t * q
        s, t = t, s
        sx -= tx * q
        sx, tx = tx, sx
        sy -= ty * q
        sy, ty = ty, sy
    return sx, sy

def calc(a, b):
    x, y = extgcd(-a, b)
    if x < 0:
        k = (-x + b - 1) // b
        x += b * k
        y += a * k
    if x == 0:
        x += b
        y += a
    if y < 0:
        k = (-y + a - 1) // a
        x += b * k
        y += a * k
    if y == 0:
        x += b
        y += a
    return x, y

N = int(input())
primes = prime_factor(2 * N)
ans = float('inf')
for S in range(1 << len(primes)):
    a = b = 1
    for i, (p, c) in enumerate(primes.items()):
        if S >> i & 1:
            a *= pow(p, c)
        else:
            b *= pow(p, c)
    x, y = calc(a, b)
    ans = min(ans, a * x)
    x, y = calc(b, a)
    ans = min(ans, b * x)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import math

# 素因数分解、辞書で返すやつ
# mathをimportする
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor

# (x, y) of ax + by = 1
def oneOfSolution(a, b):
    if b == 1:
        return 0, 1
    d = a//b
    p, q = oneOfSolution(b, a%b)
    return q, p-d*q

def solution(a, b):
    if b > a:
        y0, x0 = oneOfSolution(b, a)
    else:
        x0, y0 = oneOfSolution(a, b)
    x = x0%b
    if a*x < 2:
        x += b
    return a*x-1

N = int(input())

if N == 1:
    ans = 1
else:
    N_prime = prime(N)
    W = []
    for num, cnt in N_prime.items():
        if num == 2:
            W.append(num**(cnt+1))
        else:
            W.append(num**cnt)

    M = len(W)
    ans = N
    for bit in range(1<<M):
        a = 1; b = 1
        for i, m in enumerate(W):
            if bit&(1<<i):
                a *= m
            else:
                b *= m
        ans = min(ans, solution(a, b))

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def extgcd(a, b):
    if b:
        d, y, x = extgcd(b, a%b)
        y -= (a//b)*x
        return d, x, y
    else:
        return a, 1, 0

ans = float("inf")
n = int(input())
n = 2*n
P = primeFactor(n)
K = P.keys()
l = len(K)
for i in range(1<<l):
    temp = 1
    for j, k in enumerate(K):
        if i>>j & 1:
            temp *= k**P[k]
    if temp == 1 or temp == n:
        continue
    other = n // temp
    S = extgcd(temp, other)[1:]
    p, q = S
    if p > q:
        p, q = q, p
        temp, other = other, temp
    ans = min(ans, p*temp*(-1))
if ans == float("inf"):
    ans = n//2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import typing
def _is_prime(n: int) -> bool:
    '''
    Reference:
    M. Forisek and J. Jancina,
    Fast Primality Testing for Integers That Fit into a Machine Word
    '''

    if n <= 1:
        return False
    if n == 2 or n == 7 or n == 61:
        return True
    if n % 2 == 0:
        return False

    d = n - 1
    while d % 2 == 0:
        d //= 2

    for a in (2, 7, 61):
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = y * y % n
            t <<= 1
        if y != n - 1 and t % 2 == 0:
            return False
    return True


def _inv_gcd(a: int, b: int) -> typing.Tuple[int, int]:
    a %= b
    if a == 0:
        return (b, 0)

    # Contracts:
    # [1] s - m0 * a = 0 (mod b)
    # [2] t - m1 * a = 0 (mod b)
    # [3] s * |m1| + t * |m0| <= b
    s = b
    t = a
    m0 = 0
    m1 = 1

    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u  # |m1 * u| <= |m1| * s <= b

        # [3]:
        # (s - t * u) * |m1| + t * |m0 - m1 * u|
        # <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        # = s * |m1| + t * |m0| <= b

        s, t = t, s
        m0, m1 = m1, m0

    # by [3]: |m0| <= b/g
    # by g != b: |m0| < b/g
    if m0 < 0:
        m0 += b // s

    return (s, m0)


def _primitive_root(m: int) -> int:
    if m == 2:
        return 1
    if m == 167772161:
        return 3
    if m == 469762049:
        return 3
    if m == 754974721:
        return 11
    if m == 998244353:
        return 3

    divs = [2] + [0] * 19
    cnt = 1
    x = (m - 1) // 2
    while x % 2 == 0:
        x //= 2

    i = 3
    while i * i <= x:
        if x % i == 0:
            divs[cnt] = i
            cnt += 1
            while x % i == 0:
                x //= i
        i += 2

    if x > 1:
        divs[cnt] = x
        cnt += 1

    g = 2
    while True:
        for i in range(cnt):
            if pow(g, (m - 1) // divs[i], m) == 1:
                break
        else:
            return g
        g += 1
        
def factorize(n):
    dd = defaultdict(int)
    for i in range(2,int(n**0.5)+1):
        while n%i==0 and n>0:
            dd[i]+=1
            n//=i
    if n>1:
        dd[n]+=1
    return dd

def crt(r: typing.List[int], m: typing.List[int]) -> typing.Tuple[int, int]:
    assert len(r) == len(m)

    n = len(r)

    # Contracts: 0 <= r0 < m0
    r0 = 0
    m0 = 1
    for i in range(n):
        assert 1 <= m[i]
        r1 = r[i] % m[i]
        m1 = m[i]
        if m0 < m1:
            r0, r1 = r1, r0
            m0, m1 = m1, m0
        if m0 % m1 == 0:
            if r0 % m1 != r1:
                return (0, 0)
            continue

        # assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)

        '''
        (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));
        r2 % m0 = r0
        r2 % m1 = r1
        -> (r0 + x*m0) % m1 = r1
        -> x*u0*g % (u1*g) = (r1 - r0) (u0*g = m0, u1*g = m1)
        -> x = (r1 - r0) / g * inv(u0) (mod u1)
        '''

        # im = inv(u0) (mod u1) (0 <= im < u1)
        g, im = _inv_gcd(m0, m1)

        u1 = m1 // g
        # |r1 - r0| < (m0 + m1) <= lcm(m0, m1)
        if (r1 - r0) % g:
            return (0, 0)

        # u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)
        x = (r1 - r0) // g % u1 * im % u1

        '''
        |r0| + |m0 * x|
        < m0 + m0 * (u1 - 1)
        = m0 + m0 * m1 / g - m0
        = lcm(m0, m1)
        '''

        r0 += x * m0
        m0 *= u1  # -> lcm(m0, m1)
        if r0 < 0:
            r0 += m0

    return (r0, m0)

N = int(input())
if N==1:
    print(1)
else:
    D = factorize(N)
    D[2] += 1
    key = list(D.keys())

    m = [k**D[k] for k in key]
    ans = 2*N
    for i in range(2**len(key)):
        j = 1
        r = []
        while j < 2**len(key):
            if j&i>0:
                r.append(-1)
            else:
                r.append(0)
            j*=2
        y,z = crt(r,m)
        
        if y==0:
            y = z
        if y==1:
            continue
        ans = min(ans,y)

    print(ans)

Submission status: Accepted

Solution code:
## tmp experiment
import math


def chinese_reminder(x1, y1, x2, y2):
    g = math.gcd(y1, y2)
    if (x2 - x1) % g != 0:
        return (float("inf"), float("inf"))
    else:
        K = (x2 - x1) // g
        y1, y2 = y1 // g, y2 // g
        t = -K * modinv(y2, y1)
        m = x2 + t * g * y2
        return (m % (g * y1 * y2), g * y1 * y2)


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        return False
    else:
        return x % m


def divisors(X):
    res = set([])
    for i in range(1, X + 1):
        if i ** 2 > X:
            break
        else:
            if X % i == 0:
                res.add(i)
                res.add(X // i)
    return res


def main():

    N = int(input())
    d = divisors(2*N)
    ans = 10 ** 20
    for n in d:
        u, v = n, (2*N) // n
        if math.gcd(u, v) == 1:
            v, m = chinese_reminder(0, u, v-1, v)
            if v == 0:
                ans = min(m, ans)
            else:
                ans = min(v, ans)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def floor_sum(n, m, a, b):
    res = 0
    while True:
        if a >= m:
            res += (n - 1) * n * (a // m) // 2
            a %= m
        if b >= m:
            res += n * (b // m)
            b %= m
        y_max = (a * n + b) // m
        if y_max == 0: break
        x_max = b - y_max * m
        res += (n + x_max // a) * y_max
        n, m, a, b = y_max, a, m, x_max % a
    return res

def inv_gcd(a, b):
    a %= b
    if a == 0: return b, 0
    s = b
    t = a
    m0 = 0
    m1 = 1
    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u
        s, t = t, s
        m0, m1 = m1, m0
    if m0 < 0: m0 += b // s
    return s, m0

def inv_mod(x, m):
    assert 1 <= m
    g, im = inv_gcd(x, m)
    assert g == 1
    return im


def f(x):
  r=[]
  for i in range(2,int(x**0.5)+1):
    if x%i==0:
      r.append([i,0])
      while x%i==0:
        x//=i
        r[-1][1]+=1
  if x!=1:
    r.append([x,1])
  return r

def crt(r, m):
    assert len(r) == len(m)
    n = len(r)
    r0 = 0
    m0 = 1
    for i in range(n):
        assert 1 <= m[i]
        r1 = r[i] % m[i]
        m1 = m[i]
        if m0 < m1:
            r0, r1 = r1, r0
            m0, m1 = m1, m0
        if m0 % m1 == 0:
            if r0 % m1 != r1: return 0, 0
            continue
        g, im = inv_gcd(m0, m1)
        u1 = m1 // g
        if (r1 - r0) % g: return 0, 0
        x = (r1 - r0) // g * im % u1
        r0 += x * m0
        m0 *= u1
        if (r0 < 0): r0 += m0
    return r0, m0

N=int(input())
X=f(N*2)
if len(X)==1:
  print(2*N-1)
  exit()
X2=[X[i][0]**X[i][1] for i in range(len(X))]
Y=[1]
for i in range(len(X)):
  Y.append(Y[i]*X2[i])
P=10**20
M=len(Y)-1
for i in range(1,(1<<M)-1):
  A=[((i&(1<<j))>>j) for j in range(M)]
  P=min(P,crt(A,X2)[0])
print(P-1)

Submission status: Accepted

Solution code:
def euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
 
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
 
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
 
    return a0, b0

n=int(input())
n=n*2
soinsu=[]

num=n


for i in range(2,max(20,n)):
    if(i*i>n):
        if(num!=1):
            soinsu.append([num,1])
        break
    if(num%i!=0):
        continue
    cnt=0
    while(num%i==0):
        cnt+=1
        num//=i
    soinsu.append([i,cnt])

kazu=len(soinsu)


ans=[]
for i in range(2**(kazu-1)):
    a=1
    for j in range(kazu):
        if((i&1<<j)!=0):
            a*=soinsu[j][0]**soinsu[j][1]
    b=n//a
    c,d=euclid(a,b)
    if(c*d==0):
        c+=b
        d+=a
    ans.append(max(a*c,b*d))
    
if(kazu==1):
    print(min(ans)-2)
else:
    print(min(ans)-1)

Submission status: Accepted

Solution code:
def euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
 
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
 
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
 
    return a0, b0

n=int(input())
n*=2
soinsu=[]

num=n
for i in range(2,max(10,n)):
    if(i*i>n):
        if(num!=1):
            soinsu.append([num,1])
        break
    if(num%i!=0):
        continue
    cnt=0
    while(num%i==0):
        cnt+=1
        num//=i
    soinsu.append([i,cnt])

kazu=len(soinsu)
#print(soinsu,kazu)


ans=[]
for i in range(2**(kazu-1)):
    a=1
    for j in range(kazu):
        if((i&1<<j)!=0):
            a*=soinsu[j][0]**soinsu[j][1]
    b=n//a
    c,d=euclid(a,b)
    if(c*d==0):
        c+=b
        d+=a
    ans.append(max(a*c,b*d))
    #print(a,b,c,d)


if(kazu==1):
    print(min(ans)-2)
else:
    print(min(ans)-1)

Submission status: Accepted

Solution code:
n = int(input())
n *= 2
ans = []
ans2 = []
for i in range(2,32*10**6):
  if n % i == 0:
    ans.append(i)
    n //= i
    cnt = 1
    while n % i == 0:
      n //= i
      cnt += 1
    ans2.append(cnt)
if n != 1:
  ans.append(n)
  ans2.append(1)
#print(ans)
#print(ans2)
l = len(ans)
for i in range(l):
  ans[i] **= ans2[i]
#print(ans)
if len(ans) == 1:
  print(ans[0]-1)
  exit()
time = [0 for _ in range(l)]
def nex(time):
  for i in range(l):
    if time[i] == 0:
      time[i] = 1
      return time
    else:
      time[i] = 0
  else:
    return 'over'
can = []
while time != 'over':
  x = 1
  y = 1
  for i in range(l):
    if time[i] == 0:
      x *= ans[i]
    else:
      y *= ans[i]
  #print(x,y)
  X = int(x)
  Y = int(y)
  if x > y:
    rec = []
    while y != 1:
      rec.append(x//y)
      x,y = y,x%y
    #print(rec)
    if rec:
      le = len(rec)
      rec.reverse()
      now = [1,-rec[0]]
      for j in range(1,le):
        #print(now)
        now[0],now[1] = now[1],now[0]-now[1]*rec[j]
      #print(now)
      #print(min(abs(X*now[0]),abs(Y*now[1])))
      can.append(min(abs(X*now[0]),abs(Y*now[1])))
  time = nex(time)
print(min(can))

Submission status: Accepted

Solution code:
import math

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        return False
    else:
        return x % m

def divisors(X):
    Sets = set([])
    for i in range(1, N+1):
        if i**2 > X:
            break
        else:
            if X % i == 0:
                Sets.add(i)
                Sets.add(X//i)
    return Sets


def chinese_reminder(pair1, pair2):

    x1, y1 = pair1
    x2, y2 = pair2
    g = math.gcd(y1, y2)
    if (x2-x1) % g != 0:
        return (float("inf"), float("inf"))
    else:
        K = (x2-x1)//g
        y1, y2 = y1//g, y2//g
        t = -K*modinv(y2, y1)
        m = x2+t*g*y2
        return (m % (g*y1*y2), g*y1*y2)



N = int(input())
divs = divisors(2*N)
ans = 10**20
for n in divs:
    u, v = n, (2*N)//n
    if math.gcd(u, v) != 1:
        continue
    else:
        V,mod = chinese_reminder((0, u), (v-1, v))
        if V == 0:
            V = mod
        ans = min(V, ans)
print(ans)

Submission status: Accepted

Solution code:
def Prime_Factorization(N):
    if N<0:
        R=[[-1,1]]
    else:
        R=[]

    N=abs(N)
    k=2
    while k*k<=N:
        if N%k==0:
            C=0
            while N%k==0:
                C+=1
                N//=k
            R.append([k,C])
        k+=1

    if N!=1:
        R.append([N,1])
    if not R:
        R.append([N,1])

    return R

class Modulo_Error(Exception):
    pass

class Modulo():
    def __init__(self,a,n):
        self.a=a%n
        self.n=n

    def __str__(self):
        return "{} (mod {})".format(self.a,self.n)

    #+,-
    def __pos__(self):
        return self

    def __neg__(self):
        return  Modulo(-self.a,self.n)

    #等号,不等号
    def __eq__(self,other):
        if isinstance(other,Modulo):
            return (self.a==other.a) and (self.n==other.n)
        elif isinstance(other,int):
            return (self-other).a==0

    def __neq__(self,other):
        return not(self==other)

    #加法
    def __add__(self,other):
        if isinstance(other,Modulo):
            if self.n!=other.n:
                raise Modulo_Error("異なる法同士の演算です.")
            return Modulo(self.a+other.a,self.n)
        elif isinstance(other,int):
            return Modulo(self.a+other,self.n)

    def __radd__(self,other):
        if isinstance(other,int):
            return Modulo(self.a+other,self.n)

    #減法
    def __sub__(self,other):
        return self+(-other)

    def __rsub__(self,other):
        if isinstance(other,int):
            return -self+other

    #乗法
    def __mul__(self,other):
        if isinstance(other,Modulo):
            if self.n!=other.n:
                raise Modulo_Error("異なる法同士の演算です.")
            return Modulo(self.a*other.a,self.n)
        elif isinstance(other,int):
            return Modulo(self.a*other,self.n)

    def __rmul__(self,other):
        if isinstance(other,int):
            return Modulo(self.a*other,self.n)

    #Modulo逆数
    def inverse(self):
        return self.Modulo_Inverse()

    def Modulo_Inverse(self):
        x0, y0, x1, y1 = 1, 0, 0, 1
        a,b=self.a,self.n
        while b != 0:
            q, a, b = a // b, b, a % b
            x0, x1 = x1, x0 - q * x1
            y0, y1 = y1, y0 - q * y1

        if a!=1:
            raise Modulo_Error("{}の逆数が存在しません".format(self))
        else:
            return Modulo(x0,self.n)

    #除法
    def __truediv__(self,other):
        return self*(other.Modulo_Inverse())

    def __rtruediv__(self,other):
        return other*(self.Modulo_Inverse())

    #累乗
    def __pow__(self,m):
        u=abs(m)

        r=Modulo(pow(self.a,m,self.n),self.n)
        if m>=0:
            return r
        else:
            return r.Modulo_Inverse()

#法の合成
def __modulo_composite__(p,q):
    from math import gcd

    a,n=p.a,p.n
    b,m=q.a,q.n

    d=b-a
    g=gcd(n,m)

    if d%g:
        raise Modulo_Error("{}と{}は両立しません.".format(p,q))

    n//=g
    m//=g
    d//=g

    s=(Modulo(1,m)/Modulo(n,m)).a

    return Modulo(a+(n*g)*d*s,n*m*g)


def Modulo_Composite(*X):
    from functools import reduce
    return reduce(__modulo_composite__,X)
#=======================================
N=int(input())

if N==1:
    print(1)
    exit()

R=Prime_Factorization(N)

X=[]
for (p,e) in R:
    if p==2:
        X.append(2**(e+1))
    else:
        X.append(p**e)

Y=[Modulo(0,1) for x in X]
M=float("inf")
for s in range(1<<len(X)):
    t=s
    for k in range(len(X)):
        if t&1:
            Y[k]=Modulo(0,X[k])
        else:
            Y[k]=Modulo(-1,X[k])
        t>>=1

    Z=Modulo_Composite(*Y)
    if Z!=0:
        M=min(M,Z.a)
    else:
        M=min(M,Z.n)
print(M)

Submission status: Accepted

Solution code:
from math import gcd

from collections import Counter
from itertools import product


min2 = lambda x,y: x if x < y else y


# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def chinese_remainder_theorem(R, M, prod):
    """
    returns x s.t.
    all(x%m == r for r,m in zip(R,M))
    """
    s = 0
    for m,r in zip(M,R):
        p = prod//m
        s += r * p * modinv(p,m)
        s %= prod
    return s


# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n



N = int(input())

factors = Counter(prime_factors(N))
if factors[2] > 0:
    factors[2] += 1
    N *= 2
mods = [f**p for f,p in factors.items()]

res = N
for R in product(*((0,m-1) for m in mods)):
    t = chinese_remainder_theorem(R, mods, N)
    if t > 0:
        res = min2(res, t)

print(res)

Submission status: Accepted

Solution code:
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1<<32 else [2, 3, 5, 7, 11, 13, 17] if n < 1<<48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

def exEuclid(a, mod):
    b = mod
    s, u = 1, 0
    while b:
        q = a // b
        a, b = b, a % b
        s, u = u, s - q * u
    return a, s % mod

def crt(R, M):
    assert len(R) == len(M)
    N = len(R)
    r0, m0 = 0, 1
    for r, m in zip(R, M):
        assert m >= 1
        r %= m
        if m0 < m:
            r0, r = r, r0
            m0, m = m, m0
        if m0 % m == 0:
            if r0 % m != r: return (0, 0)
            continue
        g, im = exEuclid(m0, m)
        u = m // g
        if (r - r0) % g: return (0, 0)
        x = (r - r0) // g % u * im % u
        r0 += x * m0
        m0 *= u
        if r0 < 0: r0 += m0
    return (r0, m0)


N = int(input())
if N <= 10:
    for i in range(1, 100):
        if i * (i + 1) // 2 % N == 0:
            print(i)
            exit()
pf = primeFactor(N)
# print("pf =", pf)
L = []
for p in pf:
    L.append(p ** pf[p])
# print("L =", L)
k = len(L)
mi = 10 ** 100
for i in range(1 << k):
    R, M = [], []
    for j, m in enumerate(L):
        if i >> j & 1:
            R.append(0)
        else:
            R.append(m - 1)
        M.append(m)
    c = crt(R, M)[0]
    if c and c * (c + 1) // 2 % N == 0:
        mi = min(mi, c)
print(mi)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


def extgcd(a, b):
    if b:
        d, y, x = extgcd(b, a % b)
        y -= (a // b) * x
        return d, x, y
    return a, 1, 0


# V = [(X_i, Y_i), ...]: X_i (mod Y_i)
def remainder(V):
    x = 0; d = 1
    for X, Y in V:
        g, a, b = extgcd(d, Y)
        x, d = (Y*b*x + d*a*X) // g, d*(Y // g)
        x %= d
    return x, d


N = I()


def prime_factorization(n):
    ANS = {}
    for i in range(2,int(n**.5)+1):
        if n % i == 0:
            r = 0  # nがiで何回割り切れるか
            while n % i == 0:
                n //= i
                r += 1
            ANS[i] = r
    if n != 1:
        ANS[n] = 1
    return ANS


prime = prime_factorization(N)
if not 2 in list(prime.keys()):
    prime[2] = 1
else:
    prime[2] += 1

A = list(prime.keys())
B = list(prime.values())
l = len(A)


ans = 2*N
from itertools import product

for a in list(product([-1,0],repeat=l)):
    for i in range(l):
        if a[i] != 0:
            break
    else:
        continue

    V = [(a[i],A[i]**B[i]) for i in range(l)]
    x,d = remainder(V)
    ans = min(ans,x)

print(ans)

Submission status: Accepted

Solution code:
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

N = int(input())
N *= 2

def crt(a, n, b, m, inv):
    out = a
    #inv = pow(n, -1, m)
    out += (b - a) * n * inv
    return out % (n * m)

p = []

i = 2
while i * i <= N:
    curr = 1
    while N % i == 0:
        N//= i
        curr *= i
    if curr != 1:
        p.append(curr)
    i += 1
    
if N != 1:
    p.append(N)

poss = [0]
mod = 1
for v in p:
    new = []
    #inv = pow(mod, -1, v)
    inv = modinv(mod, v)
    for u in poss:
        new.append(crt(u, mod, 0, v, inv))
        new.append(crt(u, mod, -1, v, inv))
    poss = new
    mod *= v
poss.sort()
poss += [mod]
print(poss[1])