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

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(a*abs(x), b*abs(y))
    ans = min(ans, res)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline


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


def main():
    n = int(input())
    divisors = make_divisors(2 * n)

    ans = n-1 if n%2 else 2*n-1
    for x in divisors:
        y = n * 2 // x
        if y == 1:
            continue
        r = [0, y-1]
        m = [x, y]
        rem, mod = crt(r, m)
        if rem == mod == 0:
            continue
        ans = min(ans, rem)

    
    print(ans if n-1 else 1)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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 main(N):
    N *= 2
    div = calc_div(N).tolist()
    for a in div:
        a = int(a)
        b = N // a
        if np.gcd(a, b) != 1:
            continue
        # b | an + 1
        n = (-pow(a,-1,b)) % b
        k = a * n
        if k == 0:
            k += N
        assert k * (k + 1) % N == 0
        yield k

N = int(read())
print(min(main(N)))

Submission status: Accepted

Solution code:
from itertools import product

def main():
    n = int(input())

    # Exception Handling
    if n == 1:
        print(1)
        exit()

    # calculate the maximum answer
    if n % 2 == 0:
        ans = 2 * n - 1
        n *= 2
    else:
        ans = n - 1

    # Prime Factorization
    factors = []
    for p in range(2, n):
        if p * p > n:
            if n > 1:
                factors.append(n)
            break

        if n % p == 0:
            cnt = 0
            while n % p == 0:
                cnt += 1
                n //= p
            factors.append(p ** cnt)

    # Full Search
    # k%factor==0 or (k+1)%factor==0
    for tf in product([True, False], repeat=len(factors)):
        a, b = 1, 1
        for i in range(len(factors)):
            if tf[i]:
                a *= factors[i]
            else:
                b *= factors[i]

        if a < b or a == 1 or b == 1:
            continue

        # Euclidean Algorithm
        # a*x - b*y = 1
        l = []
        quo = []
        while a % b > 1:
            l.append(a)
            a = b
            quo.append(0)
            quo[-1], b = divmod(l[-1], b)
        x, y = 1, a//b
        flag = True
        while l:
            if flag:
                x += y * quo.pop()
                b = l.pop()
            else:
                y += x * quo.pop()
                a = l.pop()
            flag = not flag

        if ans > b * y:
            ans = b * y

    print(ans)

main()

Submission status: Accepted

Solution code:
from itertools import product

def main():
    n = int(input())
    n_copy = n

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

    if n % 2 == 0:
        ans = 2 * n - 1
        n *= 2
    else:
        ans = n - 1

    factors = []
    for p in range(2, n):
        if p * p > n:
            if n > 1:
                factors.append(n)
            break

        if n % p == 0:
            cnt = 0
            while n % p == 0:
                cnt += 1
                n //= p
            factors.append(p ** cnt)

    for tf in product([True, False], repeat=len(factors)):
        a, b = 1, 1
        for i in range(len(factors)):
            if tf[i]:
                a *= factors[i]
            else:
                b *= factors[i]

        if a == 1 or b == 1:
            continue

        if a < b:
            a, b = b, a

        # Euclidean Algorithm
        # a*x - b*y = 1
        # quotient: 商
        l = []
        quo = []
        while a % b > 1:
            l.append(a)
            a = b
            quo.append(0)
            quo[-1], b = divmod(l[-1], b)
        x, y = 1, a//b
        flag = True
        while l:
            if flag:
                x += y * quo.pop()
                b = l.pop()
            else:
                y += x * quo.pop()
                a = l.pop()
            flag = not flag

        if ans > b * y:
            ans = b * y

    print(ans)

main()

Submission status: Accepted

Solution code:
n = int(input())
if n == 1:
    print(1)
    exit()
if n == 2:
    print(3)
    exit()
n *= 2
ans = n*2

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 float("INF")
    else:
        return x % m
def calc(b1,m1,b2,m2):
    p = modinv(m1,m2)
    if p == float("INF"):
        return float("INF")
    tmp = (b2-b1)*p%m2
    m = m1*m2
    tmp = (b2-b1)*p%m2
    r = (b1+m1*tmp)%m
    return r

for i in range(1,int(n**0.5)+1):
    if n%i == 0:
        ans = min(ans,calc(0,i,n//i-1,n//i))
        if i != 1:
            ans = min(ans,calc(0,n//i,i-1,i))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
if n == 1:
    print(1)
    exit()
if n == 2:
    print(3)
    exit()
n *= 2
ans = n*2

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 float("INF")
    else:
        return x % m
def calc(b1,m1,b2,m2):
    p = modinv(m1,m2)
    if p == float("INF"):
        return float("INF")
    d = 1
    if (b2-b1)%d:
        return float("INF")
    tmp = (b2-b1)*p%m2
    m = m1*m2//d
    tmp = (b2-b1)//d*p%(m2//d)
    r = (b1+m1*tmp)%m
    return r

for i in range(1,int(n**0.5)+1):
    if n%i == 0:
        ans = min(ans,calc(0,i,n//i-1,n//i))
        if i != 1:
            ans = min(ans,calc(0,n//i,i-1,i))
print(ans)

Submission status: Accepted

Solution code:
#素因数分解、計算量はO(√N)
from collections import defaultdict
def factorize(n):
  b = 2
  dic = defaultdict(lambda: 0)
  while b * b <= n:
    while n % b == 0:
      n //= b
      dic[b] += 1
    b = b + 1
  if n > 1:
    dic[n] += 1
  return dic

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
N = int(input())
fct = factorize(2*N)
lis = []
for k,v in fct.items():
  lis.append(pow(k,v))
ans = 10**18
from itertools import groupby, accumulate, product, permutations, combinations
for pro in product([0,1],repeat=len(lis)):
  prod1 = 1
  for i,p in enumerate(pro):
    if p==1:
      prod1 *= lis[i]
  prod2 = (N*2)//prod1
  if min(prod1,prod2)>ans:
    continue
  if min(prod1,prod2)==1:
    ans = min(ans, max(prod1,prod2)-1)
  else:
    d,a1,a2 = extgcd(prod1,prod2)
    ans = min(ans, min(abs(a1*prod1),abs(a2*prod2)))
print(ans)

Submission status: Accepted

Solution code:
#素因数分解、計算量はO(√N)
from collections import defaultdict
def factorize(n):
  b = 2
  dic = defaultdict(lambda: 0)
  while b * b <= n:
    while n % b == 0:
      n //= b
      dic[b] += 1
    b = b + 1
  if n > 1:
    dic[n] += 1
  return dic

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
N = int(input())
fct = factorize(2*N)
lis = []
for k,v in fct.items():
  lis.append(pow(k,v))
ans = 10**18
from itertools import groupby, accumulate, product, permutations, combinations
for pro in product([0,1],repeat=len(lis)):
  prod1 = 1
  for i,p in enumerate(pro):
    if p==1:
      prod1 *= lis[i]
  prod2 = (N*2)//prod1
  if min(prod1,prod2)==1:
    ans = min(ans, max(prod1,prod2)-1)
  else:
    d,a1,a2 = extgcd(prod1,prod2)
    ans = min(ans, min(abs(a1*prod1),abs(a2*prod2)))
print(ans)

Submission status: Accepted

Solution code:
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 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  # -> lcm(m0, m1)
        if r0 < 0:
            r0 += m0

    return (r0, m0)

def prime_de(number):
    factor = []
    div = 2
    while div*div <= number:
        cnt = 0
        while number % div == 0:
            cnt += 1
            number //= div
        if cnt != 0:
            factor.append((div, cnt))
        div += 1
    if number > 1:
        factor.append((number, 1))
    return factor

N, = map(int, input().split())
p = prime_de(N)
lp = len(p)
R = 10**18
for i in range(2**lp):
    l = []
    for j in range(lp):
        i, m = divmod(i, 2)
        l.append(m)
    r, m = [], []
    for j in range(lp):
        a, b = p[j]
        c = a**b if a!=2 else a**(b+1)
        if l[j]:
            r.append(0)
        else:
            r.append(c-1)
        m.append(c)
    x, y = crt(r, m)
    if x:
        R = min(R, x)
    else:
        R = min(R, y)
print(R)

Submission status: Accepted

Solution code:
import math

N=int(input())

ANS=[0,1, 3, 2, 7, 4, 3, 6, 15, 8, 4, 10, 8, 12, 7, 5, 31, 16, 8, 18, 15, 6, 11, 22, 15, 24, 12, 26, 7, 28, 15, 30, 63, 11, 16, 14, 8, 36, 19, 12, 15, 40, 20, 42, 32, 9, 23, 46, 32, 48, 24, 17, 39, 52, 27, 10, 48, 18, 28, 58, 15, 60, 31, 27, 127, 25, 11, 66, 16, 23, 20, 70, 63, 72, 36, 24, 56, 21, 12, 78, 64, 80, 40, 82, 48, 34, 43, 29, 32, 88, 35, 13, 23, 30, 47, 19, 63, 96, 48, 44, 24]


if N==1:
    print(ANS[N])
    exit()


def ff(x):
    L=int(math.sqrt(x))

    FACT=dict()

    for i in range(2,L+2):
        while x%i==0:
            FACT[i]=FACT.get(i,0)+1
            x=x//i

    if x!=1:
        FACT[x]=FACT.get(x,0)+1

    return FACT

# 拡張ユークリッドの互除法.ax+by=gcd(a,b)となる(x,y)を一つ求め、(x,y)とgcd(x,y)を返す.
def Ext_Euc(a,b,axy=(1,0),bxy=(0,1)): # axy=a*1+b*0,bxy=a*0+b*1なので,a,bに対応する係数の初期値は(1,0),(0,1)
    # print(a,b,axy,bxy)
    q,r=divmod(a,b)

    if r==0:
        return bxy,b # a*bxy[0]+b*bxy[1]=b
   
    rxy=(axy[0]-bxy[0]*q,axy[1]-bxy[1]*q) # rに対応する係数を求める.
    return Ext_Euc(b,r,bxy,rxy)

FACT=ff(N*2)
LIST=[]
for f in FACT:
    LIST.append(f**FACT[f])
    
L=len(LIST)

LANS=1<<60

for i in range(1,(1<<L)-1):
    A=1
    B=1
    for j in range(L):
        if i & (1<<j)!=0:
            A*=LIST[j]
        else:
            B*=LIST[j]
    #print(A,B)
    #print(Ext_Euc(A,-B))
    x,_=Ext_Euc(A,-B)
    x,y=x[0],x[1]
    # ANS=x+B*k

    if x<0:
        x+=(1+abs(x)//B)*B
    #k=(B+x-1)//x
    #ANS=x+B*k
    #print(x,B,k,ANS)
    LANS=min(LANS,x*A)

print(LANS)

Submission status: Accepted

Solution code:
import math

N=int(input())

def ff(x):
    L=int(math.sqrt(x))

    FACT=dict()

    for i in range(2,L+2):
        while x%i==0:
            FACT[i]=FACT.get(i,0)+1
            x=x//i

    if x!=1:
        FACT[x]=FACT.get(x,0)+1

    return FACT

# 拡張ユークリッドの互除法.ax+by=gcd(a,b)となる(x,y)を一つ求め、(x,y)とgcd(x,y)を返す.
def Ext_Euc(a,b,axy=(1,0),bxy=(0,1)): # axy=a*1+b*0,bxy=a*0+b*1なので,a,bに対応する係数の初期値は(1,0),(0,1)
    # print(a,b,axy,bxy)
    q,r=divmod(a,b)

    if r==0:
        return bxy,b # a*bxy[0]+b*bxy[1]=b
   
    rxy=(axy[0]-bxy[0]*q,axy[1]-bxy[1]*q) # rに対応する係数を求める.
    return Ext_Euc(b,r,bxy,rxy)

FACT=ff(N*2)
LIST=[]
for f in FACT:
    LIST.append(f**FACT[f])
    
L=len(LIST)

LANS=2*N-1

for i in range(1<<L):
    A=1
    B=1
    for j in range(L):
        if i & (1<<j)!=0:
            A*=LIST[j]
        else:
            B*=LIST[j]
    if A==1 or B==1:
        continue

    x,_=Ext_Euc(A,-B)
    x,y=x[0],x[1]

    if x<0:
        x+=(1+abs(x)//B)*B

    LANS=min(LANS,x*A)

print(LANS)

Submission status: Accepted

Solution code:
#素因数分解、計算量はO(√N)
from collections import defaultdict
def factorize(n):
  b = 2
  dic = defaultdict(lambda: 0)
  while b * b <= n:
    while n % b == 0:
      n //= b
      dic[b] += 1
    b = b + 1
  if n > 1:
    dic[n] += 1
  return dic
N = int(input())
fct = factorize(2*N)
lis = []
for k,v in fct.items():
  lis.append(pow(k,v))
ans = 10**18
from itertools import groupby, accumulate, product, permutations, combinations
for pro in product([1,0],repeat=len(lis)):
  prod1 = 1
  for i,p in enumerate(pro):
    if p==1:
      prod1 *= lis[i]
  prod2 = (N*2)//prod1
  if prod1<prod2:
    prod1,prod2 = prod2,prod1
    # continue
  for i in range(1,prod2+1):
    if prod1*i>ans:
      break
    if (prod1*i-1)%prod2==0:
      ans = min(ans, prod1*i-1)
      break
    if (prod1*i+1)%prod2==0:
      ans = min(ans, prod1*i)
      break
print(ans)

Submission status: Accepted

Solution code:
#素因数分解、計算量はO(√N)
from collections import defaultdict
def factorize(n):
  b = 2
  dic = defaultdict(lambda: 0)
  while b * b <= n:
    while n % b == 0:
      n //= b
      dic[b] += 1
    b = b + 1
  if n > 1:
    dic[n] += 1
  return dic
N = int(input())
fct = factorize(2*N)
lis = []
for k,v in fct.items():
  lis.append(pow(k,v))
ans = 10**18
from itertools import groupby, accumulate, product, permutations, combinations
for pro in product([1,0],repeat=len(lis)):
  prod1 = 1
  for i,p in enumerate(pro):
    if p==1:
      prod1 *= lis[i]
  prod2 = (N*2)//prod1
  if prod1<prod2:
    # prod1,prod2 = prod2,prod1
    continue
  for i in range(1,prod2+1):
    if prod1*i>ans:
      break
    if (prod1*i-1)%prod2==0:
      ans = min(ans, prod1*i-1)
      break
    if (prod1*i+1)%prod2==0:
      ans = min(ans, prod1*i)
      break
print(ans)

Submission status: Accepted

Solution code:
#素因数分解、計算量はO(√N)
from collections import defaultdict
def factorize(n):
  b = 2
  dic = defaultdict(lambda: 0)
  while b * b <= n:
    while n % b == 0:
      n //= b
      dic[b] += 1
    b = b + 1
  if n > 1:
    dic[n] += 1
  return dic
N = int(input())
fct = factorize(2*N)
lis = []
for k,v in fct.items():
  lis.append(pow(k,v))
lis.sort(reverse=True)
ans = 10**18
from itertools import groupby, accumulate, product, permutations, combinations
for pro in product([1,0],repeat=len(lis)):
  prod1 = 1
  for i,p in enumerate(pro):
    if p==1:
      prod1 *= lis[i]
  prod2 = (N*2)//prod1
  if prod1<prod2:
    # prod1,prod2 = prod2,prod1
    continue
  for i in range(1,prod2+1):
    if prod1*i>ans:
      break
    if (prod1*i-1)%prod2==0:
      ans = min(ans, prod1*i-1)
      break
    if (prod1*i+1)%prod2==0:
      ans = min(ans, prod1*i)
      break
print(ans)

Submission status: Accepted

Solution code:
#素因数分解、計算量はO(√N)
from collections import defaultdict
def factorize(n):
  b = 2
  dic = defaultdict(lambda: 0)
  while b * b <= n:
    while n % b == 0:
      n //= b
      dic[b] += 1
    b = b + 1
  if n > 1:
    dic[n] += 1
  return dic
N = int(input())
fct = factorize(2*N)
lis = []
for k,v in fct.items():
  lis.append(pow(k,v))
ans = 10**18
from itertools import groupby, accumulate, product, permutations, combinations
for pro in product([0,1],repeat=len(lis)):
  prod1 = 1
  for i,p in enumerate(pro):
    if p==1:
      prod1 *= lis[i]
  if prod1==1:
    continue
  prod2 = (N*2)//prod1
  if prod1<prod2:
    continue
  
  for i in range(1,prod2+1):
    if prod1*i>ans:
      break
    if (prod1*i-1)%prod2==0:
      ans = min(ans, prod1*i-1)
      break
    if (prod1*i+1)%prod2==0:
      ans = min(ans, prod1*i)
      break

print(ans)

Submission status: Accepted

Solution code:
#素因数分解、計算量はO(√N)
from collections import defaultdict
def factorize(n):
  b = 2
  dic = defaultdict(lambda: 0)
  while b * b <= n:
    while n % b == 0:
      n //= b
      dic[b] += 1
    b = b + 1
  if n > 1:
    dic[n] += 1
  return dic
N = int(input())
fct = factorize(2*N)
lis = []
for k,v in fct.items():
  lis.append(pow(k,v))
ans = 10**18
from itertools import groupby, accumulate, product, permutations, combinations
for pro in product([0,1],repeat=len(lis)):
  prod1 = 1
  for i,p in enumerate(pro):
    if p==1:
      prod1 *= lis[i]
  if prod1==1:
    continue
  prod2 = (N*2)//prod1
  if prod1<prod2:
    prod1,prod2 = prod2,prod1
  
  for i in range(1,prod2+1):
    if prod1*i>ans:
      break
    if (prod1*i-1)%prod2==0:
      ans = min(ans, prod1*i-1)
      break
    if (prod1*i+1)%prod2==0:
      ans = min(ans, prod1*i)
      break

print(ans)

Submission status: Accepted

Solution code:
def mod_inv(a, MOD):
    """ 前提: aとMODが互いに素であること """
    b = MOD
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        u -= t * v
        a, b = b, a
        u, v = v, u
    u %= MOD
    return u


def prime_factorize(n):
    i = 2
    res = {}
    while i * i <= n:
        if n % i != 0:
            i += 1
            continue
        res[i] = 0
        while n % i == 0:
            res[i] += 1
            n //= i
        i += 1
    if n != 1:
        res[n] = 1
    return res


def solve(n):
    n *= 2
    pf = prime_factorize(n)
    l = len(pf)
    pfk = []
    for i, p in enumerate(pf):
        pfk.append(p ** pf[p])

    ans = 10 ** 18

    for bit in range(1 << l):
        a = 1
        for d in range(l):
            if bit & (1 << d):
                a *= pfk[d]
        b = n // a

        if a == 1:
            k = n - 1
        elif b == 1:
            k = n
        else:
            m = mod_inv(b, a)
            k = b * m - 1
        ans = min(ans, k)

    return ans


n = int(input())
ans = solve(n)
print(ans)

# import random
#
# for n in range(1, 10000):
#     a = solve(n)
#     i = -1
#     for i in range(1, 2 * n + 1):
#         if i * (i + 1) // 2 % n == 0:
#             break
#     # print(n, a, i)
#     assert a == i

Submission status: Accepted

Solution code:
def crt(R, M):
    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
    assert len(R) == len(M)
    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)


def atcoder_acl1_b():
    N = int(input())
    def divisor(n):
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                yield i
                if i != n // i:
                    yield n // i

    ans = 10**20
    for x in divisor(2*N):
        kc, _ = crt([0, -1], (x, 2*N//x))
        if kc != 0:
            ans = min(ans, kc)
    print(ans)


if __name__ == '__main__':
    atcoder_acl1_b()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 50


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


def divisor(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            yield i
            if i != n // i:
                yield n // i


def crt(R, M):
    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
    assert len(R) == len(M)
    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)


@mt
def slv(N):
    ans = INF
    for x in divisor(2*N):
        kc, _ = crt([0, -1], (x, 2*N//x))
        if kc != 0:
            ans = min(ans, kc)
    return ans


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 50


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


def divisor(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            yield i
            if i != n // i:
                yield n // i


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)

@mt
def slv(N):
    ans = INF
    for x in divisor(2*N):
        kc, _ = crt([0, -1], (x, 2*N//x))
        if kc != 0:
            ans = min(ans, kc)
    return ans


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 50


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


def divisor(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            yield i
            if i != n // i:
                yield n // i


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)

@mt
def slv(N):
    def f(n):
        return (n+1)*n // 2

    cand = list(divisor(2*N))
    cand.sort()
    ans = INF
    for x in cand:
        kc, _ = crt([0, -1], (x, 2*N//x))
        if kc != 0:
            ans = min(ans, kc)
    return ans


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
def gcd(x, y):
  k, l = x, y
  while l:
    k, l = l, k % l
  return k
def factorization(n):
  a = n
  p = 2
  D = {}
  while a != 1:
    cnt = 0
    while a % p == 0:
      cnt += 1
      a //= p
    if cnt:
      D[p] = cnt
    p += 1
    if p * p > n and a != 1:
      D[a] = 1
      break
  return D
X = factorization(2*N)
F = {1}
for i in X:
  tmp = set()
  for j in F:
    tmp.add(j)
    p = j
    for k in range(X[i]):
      tmp.add(p*i)
      p *= i
  for j in tmp:
    F.add(j)
def extgcd(a, b, c):
  x, y, u, v, k, l = 1, 0, 0, 1, a, b
  while l:
    x, y, u, v, k, l = u, v, x - u * (k // l), y - v * (k // l), l, k % l
  return c*x, c*y
m = 2*N+1
for i in F:
  if gcd(i, (2*N)//i) == 1:
    x, y = extgcd((2*N)//i, -i, 1)
    while x <= 0 or y <= 0:
      x += i
      y += (2*N)//i
    m = min(x*((2*N)//i), m)
print(m)

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict
from itertools import chain, combinations


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


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 solve(n):
    if n == 1:
        return 1
    factors = calc_div(2 * n)
    # print(factors)
    # trivial answer
    res = 2 * n - 1

    # power set
    for p in factors:
        q = (2 * n) // p
        if p == 1 or q == 1:
            continue
        a, x, y = ext_gcd(p, q)
        if a > 1:
            continue
        if x < 0:
            res = min(res, abs(p * x))
        else:
            res = min(res, abs(q * y))
        # print(p, q, p * x, q * y)
    # print(res)
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(11) == 10
    assert solve(20200920) == 1100144


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