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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
ざっくり見積もってもkは√N以上

1+2+...+k=Sとおく

Nが2冪なら，k=2*N-1ぽい．(k*(k+1))//2で，k,k+1の片方は奇数なのでどちらかで十分な数の2を因数に用意する必要があるのであってそう

Nが奇数なら，k=N-1でS=(N*(N-1))//2 はいける．それよりも下を探したい．
S=aNとおけばa<=(N-1)//2 で，aさえ決め打てばkを√(2aN)付近で探せたりするけど，aの範囲が広い...
また，k,k+1の片方は偶数なのでaは偶数
保留

Nが偶数なら，k=2N-1でS=(2N*(2N-1))//2 はいける．それよりも下を探したい．
素因数分解した時の2の個数をm-1個として，
k,k+1のどちらかに2をm個を持たせる必要がある(÷2させるので一つ多く)．
つまり，pow(2,m)*b,pow(2,m)*b±1のような形になるはず．
Nを2で割り続けて，残ったものがb*(pow(2,m)*b±1)とか考えたけど，
aNのaが偶数になるケースとかやばい，(N=14でk,k+1=7,8)

これ，2冪の時と同様の議論が3冪とかでもできるか．
k,k+1が互いにそなので，素因数は固めるべき．
なので，まずはNを素因数分解する，そんで持って素因数毎に固めて,k,k+1候補(a,b)を作る，小さい方をx倍していき，差が1になれば完成．
これは素因数毎にbit全探索でいける．素因数の種類は20もないでしょ．2,3,5,7...と行けば10^15はすぐ到達する．素数小さい方から15個くらいかけると10^15．

いやー，小さい方をx倍，大きい方をy倍して初めてNの倍数という可能性も．
ax-by=1なら良いので拡張ユークリッドか


N=1ならk=1
"""
def main():

    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)
    #[(p1,n1),(p2,n2),...]の形で返す
    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


    #約数列挙
    #10^6以下で約数の数が最大なのは720720の時(240個しかない！)
    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 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



    mod=10**9+7
    N=I()
    if N==1:
        print(1)
        exit()
    
    pf=primeFactor(N)
    M=len(pf)
    
    L=[]
    for p in pf:
        n=pf[p]
        if p==2:
            n+=1#あとで割る2する分
        L.append(pow(p,n))
    
    if N%2==1:
        ans=N-1
    else:
        ans=2*N-1    
    
    import itertools
    for ite in itertools.product([0,1], repeat=M):
        a=1
        b=1
        for i in range(M):
            if ite[i]==0:
                a*=L[i]
            else:
                b*=L[i]
        
        # ax-by=1
        g,x,y=egcd(a,-b)
        temp=min(abs(a*x), abs(b*y))
        if temp!=0:
            ans=min(ans,temp)
        
    print(ans)
                
        


main()

Submission status: Accepted

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

# 二元の場合の中国剰余定理
# x≡b1(mod m1)かつx≡b2(mod m2)⇔x≡r(mod m)となる(r,m)を返す
# 解なしの時(0,-1)
def crt(b1,m1,b2,m2):
    d,p,q=exgcd(m1,m2)
    if (b2-b1)%d!=0 or d!=1:
        return 0,-1
    m=m1*(m2//d) # m=lcm(m1,m2)
    tmp=(b2-b1)//d*p%(m2//d)
    r=(b1+m1*tmp)%m
    return r,m

ans=10**18
for num in range(1,2*n+1):
    if num*num>2*n:
        break
    if 2*n%num==0:
        r1,m1=crt(0,num,-1,2*n//num)
        r2,m2=crt(0,2*n//num,-1,num)
        if r1!=0:
            ans=min(r1,ans)
        if r2!=0:
            ans=min(r2,ans)
print(ans)

Submission status: Accepted

Solution code:
def inv_gcd(a, b):
    a = (a + b) % b
    if a == 0:
        return (b, 0)
    s, t = b, a
    m0, m1 = 0, 1
 
    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u
 
        tmp = s
        s = t
        t = tmp
        tmp = m0
        m0 = m1
        m1 = tmp
    
    if m0 < 0:
        m0 += b // s
    return (s, m0)
 
 
def crt(r, m):
    n = len(r)
    r0, m0 = 0, 1
 
    for i in range(n):
        r1, m1 = (r[i] + m[i]) % m[i], m[i]
 
        if m0 < m1:
            m0, m1 = m1, m0
            r0, r1 = r1, r0
        
        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 % u1 * im % u1
 
        r0 += x * m0
        m0 *= u1
        if (r0 < 0):
            r0 += m0
        
    return (r0, m0)


def divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  divisors.sort()
  return divisors


# print(divisors(z))

z=int(input())


ans = z-1 if z%2 else 2*z-1
for i in divisors(2*z):
  y=2*z//i
  if y == 1:
    continue
  a=[0,-1]
  b=[i,y]
  rem, mod = crt(a, b)
  #print(rem)
  #print(mod)
  if rem == mod == 0:
      continue
  ans = min(ans, rem)

print(ans if z-1 else 1)

Submission status: Accepted

Solution code:
n=int(input())
def fct(x):
    res=[]
    sq=int(x**(1/2))+7
    if x%2==0:
        cnt=1
        while x%2==0:
            cnt*=2
            x//=2
        res.append(cnt)
    for i in range(3,sq,2):
        if x%i==0:
            cnt=1
            while x%i==0:
                cnt*=i
                x//=i
            res.append(cnt)
    if x>1:
        res.append(x)
    res=list(set(res))
    return res


#https://tex2e.github.io/blog/crypto/crt
from functools import reduce
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:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def chinese_remainder(a, n):
    # a := [a1, a2, ..., ak]
    # n := [n1, n2, ..., nk]
    total = 0
    prod = reduce(lambda x, y: x*y, n)
    for n_i, a_i in zip(n, a):
        b_i = prod // n_i
        total += a_i * b_i * modinv(b_i, n_i)
    return total % prod

p=fct(2*n)
l=len(p)
bit=1<<l
k=10**20
for i in range(bit):
    f1=1;f2=1
    for j in range(l):
        if (i>>j)&1:
            f1*=p[j]
        else:
            f2*=p[j]
    tmp=chinese_remainder([0,-1],[f1,f2])
    if tmp:
        k=min(k,tmp)
print(k)

Submission status: Accepted

Solution code:
from math import gcd

def euclid(A,B):
    if B==1:
        return 1,1-A
    else:
        q,r = A//B,A%B
        x1,y1 = euclid(B,r)
        return y1,x1-q*y1

N = int(input())
ans = 2*N
for i in range(1,2*N+1):
    if i**2>(2*N):
        break
    if (2*N)%i:
        continue

    A,B = i,(2*N)//i

    if gcd(A,B)!=1:
        continue

    x0,y0 = euclid(A,B)

    limit1 = (1-y0)//A
    if limit1*A+y0<1:
        limit1+=1

    limit2 = (x0+1)//B
    if limit2*B- x0<1:
        limit2+=1

    limit = max(limit1,limit2)

    tmp = (B*limit-x0)*A
    ans = min(ans,tmp)

    A,B = (2*N)//i,i

    x0,y0 = euclid(A,B)

    limit1 = (1-y0)//A
    if limit1*A+y0<1:
        limit1+=1

    limit2 = (x0+1)//B
    if limit2*B- x0<1:
        limit2+=1

    limit = max(limit1,limit2)

    tmp = (B*limit-x0)*A
    ans = min(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def calc_div(N):
    sq = int(N**.5 + 10)
    x = np.arange(1, sq)
    x = x[N % x == 0]
    x = np.concatenate((x, N // x))
    return np.unique(x)

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 gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

def is_pow(n):
  cnt=0
  for i in range(100):
    if n&(2**i):
      cnt+=1
  if cnt==1:
    return True
  else:
    return False

n=int(input())
if is_pow(n)==True:
  print(2*n-1)
  exit()
div=calc_div(n*2)
ans=10**18
for val in div:
  a=val
  b=(2*n)//val
  if a==1 or b==1 or gcd(a,b)!=1:
    continue
  _,x,y=xgcd(a,b)
  tmp=min(abs(a*x),abs(b*y))
  ans=min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import typing
def _is_prime(n):
    '''
    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, b):
    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, m):
    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:
from collections import defaultdict

def _is_prime(n):
    '''
    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, b):
    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, m):
    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:
import sys
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]  

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

# return [g, x, y]
# g = gcd(a, b)
# x, y satisfies a x + b y = g
def extgcd(a, b):
    if b == 0:
        return [a, 1, 0]
    g, x, y = extgcd(b, a%b)
    return [g, y, x - a//b * y]

# eq0: x = a0 (mod m0)
# eq1: x = a1 (mod m1)
# returns [xt, mod] such that x = xt + k mod for integer k.
def crt(eq0, eq1):
    a0, m0 = eq0
    a1, m1 = eq1

    g = gcd(m0, m1)

    if a0 % g != a1 % g:
        return [-1, -1]
        #raise Exception("x doesn't exist.")

    if g > 1:
        m0 //= g
        m1 //= g

        while True:
            gt = gcd(m0, g)
            if gt == 1:
                break
            m0 *= gt
            g //= gt
        
        m1 *= g

        a0 %= m0
        a1 %= m1

    g, p, q = extgcd(m0, m1)
    
    x = a0 * q * m1 + a1 * p * m0
    mod = m0 * m1
    x = x % mod

    return [x, mod]

# 本処理
N = int(input())
divs = make_divisors(2*N)
"""
if N == 1:
  print(1)
  sys.exit()
"""

ans = INF = 10**20
for x in divs:
  y = 2*N // x
  xt, mod = crt([0,x], [-1,y])
  if x == 2*N or xt == -1:
    continue
  #print(x, y, xt)
  ans = min(ans, xt)
  
print(ans)

Submission status: Accepted

Solution code:
def inv_gcd(a,b):
    a=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
    z=inv_gcd(x,m)
    assert z[0]==1
    return z[1]
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 % u1*im%u1
        r0+=x*m0
        m0*=u1
        if r0<0:
            r0+=m0
    return (r0,m0)
N=int(input())
def divide(n):
    res=[]
    i=1
    while(i*i<=n):
        if n%i==0:
            res.append(i)
            if i*i!=n:
                res.append(n//i)
        i+=1
    return res
ans=2*N
for b in divide(2*N):
    c=(2*N)//b
    tmp=crt([0,c-1],[b,c])
    if tmp==(0,0):
        continue
    x=tmp[0]
    if x==0:
        x=tmp[1]
    ans=min(x,ans)
print(ans)

Submission status: Accepted

Solution code:
from math import ceil

n = int(input())
import math
import decimal
import collections
import itertools
import sys
import random
#Union-Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for i in range(self.n)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.par[p] += self.par[q]
        self.par[q] = p
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.par[self.find(x)]

#素数関連
def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True
#Prime-Factorize
def prime_factorize(n):
    res = []
    while n % 2 == 0:
        res.append(2)
        n //= 2
    f = 3
    while f ** 2 <= n:
        if n % f == 0:
            res.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        res.append(n)
    return res
#nCr
mod = 10 ** 9 + 7
class nCr():
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod
#拡張Euclidの互除法
def extgcd(a, b, d = 0):
    g = a
    if b == 0:
        x, y = 1, 0
    else:
        x, y, g = extgcd(b, a % b)
        x, y = y, x - a // b * y
    return x, y, g
#BIT
class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (self.n + 1)
    def add(self, i, x):
        while i <= self.n:
            self.BIT[i] += x
            i += i & -i
    def query(self, i):
        res = 0
        while i > 0:
            res += self.BIT[i]
            i -= i & -i
        return res
#Associative Array
class AssociativeArray():
    def __init__(self, q):
        self.dic = dict()
        self.q = q
    def solve(self):
        for i in range(self.q):
            Query = list(map(int, input().split()))
            if Query[0] == 0:
                x, y, z = Query
                self.dic[y] = z
            else:
                x, y = Query
                if y in self.dic:
                    print(self.dic[y])
                else:
                    print(0)
#Floor Sum
def floor_sum(n, m, a, b):
    res = 0
    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
    x_max = y_max * m - b
    if y_max == 0:
        return res
    res += y_max * (n + (-x_max // a))
    res += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return res
#Z-Algorithm
def z_algorithm(s):
    str_len = len(s)
    res = [0] * str_len
    res[str_len - 1] = str_len
    i, j = 1, 0
    while i < str_len:
        while i + j < str_len and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < str_len and j > res[k] + k:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
class Manacher():
    def __init__(self, s):
        self.s = s
    def coustruct(self):
        i, j = 0, 0 
        s_len = len(self.s)
        res = [0] * s_len
        while i < s_len:
            while i - j >= 0 and i + j < s_len and self.s[i - j] == self.s[i + j]:
                j += 1
            res[i] = j
            k = 1
            while i - k >= 0 and k + res[i - k] < j:
                k += 1
            i += k
            j -= k
#mod-sqrt
def mod_sqrt(a, p):
    if a == 0:
        return 0
    if p == 2:
        return 1
    k = (p - 1) // 2
    if pow(a, k, p) != 1:
        return -1
    while True:
        n = random.randint(2, p - 1)
        r = (n ** 2 - a) % p
        if r == 0:
            return n
        if pow(r, k, p) == p - 1:
            break
    k += 1
    w, x, y, z = n, 1, 1, 0
    while k:
        if k % 2:
            y, z = w * y + r * x * z, x * y + w * z
        w, x = w * w + r * x * x, 2 * w * x
        w %= p
        x %= p
        y %= p
        z %= p
        k >>= 1
    return y
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
ans = float("inf")
div = make_divisors(2 * n)
for i in div[:ceil(len(div) / 2)]:
    x1, y1, g1 = extgcd(i, 2 * n // i)
    if g1 == 1:
        x1 *= -1
        while x1 <= 0:
            x1 += 2 * n // i
            y1 += i
        ans = min(ans, x1 * i)
    x2, y2, g2 = extgcd(2 * n // i, i)
    if g2 == 1:
        x2 *= -1
        while x2 <= 0:
            x2 += i
            y2 += 2 * n // i
        ans = min(ans, x2 * (2 * n // i))
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())

if n == 1:
    print(1)
    exit(0)

N = 2 * n


def list_divs(x):
    divs = []
    for y in range(2, int(x ** 0.5) + 1):
        if x % y == 0:
            divs.append(y)
            if y != x // y:
                divs.append(x // y)
    divs.sort()
    return divs


def chineserem(r1, m1, r2, m2):
    c0, c1 = m1, m2
    a0, a1 = 1, 0
    b0, b1 = 0, 1
    while c1:
        a0, a1 = a1, a0 - c0 // c1 * a1
        b0, b1 = b1, b0 - c0 // c1 * b1
        c0, c1 = c1, c0 % c1
    return (r1 * m2 * b0 + r2 * m1 * a0) % (m1 * m2)


divs = list_divs(N)

ans = float("inf")
for a in divs:
    b = N // a
    if gcd(a, b) == 1:
        tmp = chineserem(0, a, -1, b)
        ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import math
def extgcd(a, b):
    """
    ax + by = gcd(a,b) = d となる (x,y,d) を返す
    """
    if b == 0:
        return (1, 0, a)
    q, r = a // b, a % b
    x, y, d = extgcd(b, r)
    s, t = y, x - q * y
    return s, t, d

def inv_mod(a, N):
    """
    ax = 1 mod N となる x を返す
    """
    return extgcd(a, N)[0]

def CRT(a_1, a_2, m_1, m_2):
    """
    x = a_1 mod m_1, x = a_2 mod m_2 となる x を返す
    """
    y = (a_2 - a_1) * inv_mod(m_1, m_2) % m_2
    return a_1 + m_1 * y

N = int(input())
N *= 2
K = [[1, N]]
for i in range(2, max(int(N**0.5)+1, 2)):
    if N % i == 0:
        K.append([i, N//i])

ans = float("inf")
for i in range(len(K)):
    a, b = K[i]
    if math.gcd(a, b) == 1:
        P = CRT(0, -1, a, b)
        if P != 0:
            ans = min(P, ans)
        Q = CRT(0, -1, b, a)
        if Q != 0:
            ans = min(Q, ans)

print(ans)

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    for i in range(2, int(sqrt(num))+1):
        while num % i == 0:
            num //= i
            d[i] += 1
        if num == 1:
            break
    if num != 1:
        d[num] += 1
    return d

def extgcd(a, b, x, y):
    """ 拡張ユークリッドの互除法(ax+by=gcd(a, b)の解を求める) """

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

N = INT()

fact = list(factorize(N*2).items())
M = len(fact)

ans = N
for bit in range(1<<M):
    a = b = 1
    for i in range(M):
        if (bit>>i) & 1:
            a *= fact[i][0] ** fact[i][1]
        else:
            b *= fact[i][0] ** fact[i][1]
    y, x = extgcd(a, b, 0, 0)
    if x == 0 or y == 0:
        continue
    res = min(abs(a*x), abs(b*y))
    ans = min(ans, res)
print(ans)