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

Solution (Python):
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)
    
    
    res = 2 * n - 1

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

Solution (Python):
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):
    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
        

        if k > 0 and k * (k + 1) // 2 % n == 0:
            ans = min(ans, k)
        else:
            ans = min(ans, k + n)

    return ans


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

Solution (Python):
from collections import defaultdict
from subprocess import Popen, PIPE
from itertools import chain, combinations
import numpy as np


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 fast_prime_factorization(n):
    
    return list(map(int, Popen(["factor", str(n)], stdout=PIPE).communicate()[0].split()[1:]))


def solve(n):
    factorization_acl = fast_prime_factorization(2 * n)
    factorization = defaultdict(int)
    for f in factorization_acl:
        factorization[f] += 1
    
    factor_list = []
    for k in factorization.keys():
        factor_list.append(k ** factorization[k])

    
    res = 2 * n - 1

    
    for s in chain.from_iterable(combinations(factor_list, r) for r in range(len(factor_list) + 1)):
        p = np.int(np.prod(s))
        q = 2 * n // p
        if p == 1 or q == 1:
            continue
        a, x, y = ext_gcd(p, q)
        if x < 0:
            res = min(res, abs(p * x))
        else:
            res = min(res, abs(q * y))
        
    
    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()

Solution (Python):
from math import sqrt
from collections import deque
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
N=int(input())
def gcd_ext(a, b):
    x, y, lastx, lasty = 0, 1, 1, 0
    while b != 0:
        q = a // b
        a, b = b, a % b
        x, y, lastx, lasty = lastx - q * x, lasty - q * y, x, y
    return (lastx, lasty)
l=[]
pf={}
m=N*2
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1

keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])

d=deque()
d.append([])

for i in range(len(l)):
    x=list(range(values[i]+1))
    d2 = deque()
    
    while len(d)>0:
        l=d.popleft()
        for j in x:
            l2=l[:]
            l2.append(j)
            d2.append(l2)
    d=d2
    
ans=float("inf")
x=0
y=0
while len(d)>0:
    l=d.popleft()
    num=1
    res=1
    for i in range(len(l)):
        num=num*pow(keys[i],l[i])
        res=res*pow(keys[i],values[i]-l[i])
    
    
    if ggcd(num,res)==1:
        
        x,y=gcd_ext(num,res)
        if (x==0)or(y==0):
            x1=x+num*res
            y1=y+num+res
            ans=min(ans,x1*num-1)
            x2=x-num*res
            y2=x-num*res
            ans=min(ans,-x2*num)
        else:
            if x>y:
                ans=min(ans,x*num-1)
                x1=x-num*res
                ans=min(ans,-x1*num)
            else:
                x1=x+num*res
                ans=min(ans,x1*num-1)
                ans=min(ans,-x*num)
print(ans)

Solution (Python):
import sys
from itertools import product
def I(): return int(sys.stdin.readline().rstrip())


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



def remainder(V):
    x = 0; d = 1
    for X, Y in V:
        g, a, b = ext_gcd(d, Y)
        x, d = (Y*b*x + d*a*X) // g, d*(Y // g)
        x %= d
    return x, d


def prime_factorization(n):
    res = {}
    for i in range(2,int(n**.5)+1):
        if n % i == 0:
            r = 0  
            while n % i == 0:
                n //= i
                r += 1
            res[i] = r
    if n != 1:
        res[n] = 1
    return res


N = I()

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





A = list(prime_fac.keys())
l = len(A)

ans = 2*N

for a in list(product([-1,0],repeat=l)):
    V = [(a[i],A[i]**prime_fac[A[i]]) for i in range(l)]
    x,d = remainder(V)
    if x != 0:
        ans = min(ans,x)

print(ans)

Solution (Python):
from collections import Counter




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 chineseRem(b1, m1, b2, m2):
    
    
    
    
    d, p, q = egcd(m1, m2)
    if (b2 - b1) % d != 0:
        return 0, -1
    m = m1 * (m2 // d)  
    tmp = (b2-b1) // d * p % (m2 // d)
    r = (b1 + m1 * tmp) % m
    return r, m


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


N = int(input())
p = prime_factorize(2*N)
c = Counter(p)

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

if len(c.keys()) == 1:
    print(N-1)
    exit()

d = [k ** v for k, v in c.items()]

m = len(d)

ans = N-1
for i in range(2 ** m):
    a, b = 1, 1
    for j in range(m):
        if (i >> j) & 1:
            a *= d[j]
        else:
            b *= d[j]

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

    ans = min(ans, chineseRem(0, a, b-1, b)[0])
    ans = min(ans, chineseRem(a-1, a, 0, b)[0])

print(ans)

Solution (Python):

def inv_gcd(a, b):
  a = a % 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
    s, t = t, s
    m0, m1 = m1, m0
  if m0 < 0: m0 += b // s
  return (s, m0)

import math
def prime(x):
  p = {}
  last = math.floor(x ** 0.5)
  if x % 2 == 0:
    cnt = 1
    x //= 2
    while x & 1 == 0:
      x //= 2
      cnt += 1
    p[2] = cnt
  for i in range(3, last + 1, 2):
    if x % i == 0:
      x //= i
      cnt = 1
      while x % i == 0:
        cnt += 1
        x //= i
      p[i] = cnt
  if x != 1:
    p[x] = 1
  return p

N = int(input())

N *= 2
p = prime(N)
L = []
for key in p.keys():
  L.append(key)

M = len(L)
ans = N - 1
for i in range(1, (1 << M) - 1):
  x = 1
  cnt = 0
  while i:
    if i & 1:
      key = L[cnt]
      x *= pow(key, p[key])
    i >>= 1
    cnt += 1
  y = N // x
  iv = inv_gcd(x, y)[1]
  if iv == 0: continue
  ans = min(ans, iv * x - 1)

print(ans)

Solution (Python):
N = int(input())
pf={}
m=2*N
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1

pL = list(pf.keys())
NpL = len(pL)
import itertools
Ls = list(itertools.product([0,1], repeat=NpL))

out = N
for i in range(len(Ls)):
    L = Ls[i]
    X = 1
    Y = 1
    for j in range(NpL):
        if L[j]==1:
            X *= pL[j]**pf[pL[j]]
        else:
            Y *= pL[j]**pf[pL[j]]

    R = [X,Y]            
    R.sort(); R.reverse()   
    Q = [0]
    a,b = R[0],R[1]
    while b!=0:
        Q.append(a//b)
        R.append(a%b)
        a,b = b, a%b

    q = list(reversed(Q))
    n = len(Q)
    c = [0,1]+[0]*(n-2)
    for i in range(2,n):
        c[i] = q[i-1]*c[i-1]+c[i-2]
    C = list(reversed(c))
    if C[0]>=1 and C[1]>=1:
        cand1 = C[0]*X
        cand2 = C[0]*X-1
        if (cand1*(cand1+1))%(2*N)==0:
            out = min(out,cand1)
        if (cand2*(cand2+1))%(2*N)==0:
            out = min(out,cand2)

print(out)

Solution (Python):
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<=100:
    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


def Ext_Euc(a,b,axy=(1,0),bxy=(0,1)): 
    
    q,r=divmod(a,b)

    if r==0:
        return bxy,b 
   
    rxy=(axy[0]-bxy[0]*q,axy[1]-bxy[1]*q) 
    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]
    
    
    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)

Solution (Python):
from itertools import groupby

N = int(input())
def fast_prime_factorization(n):
    
    from subprocess import Popen, PIPE
    return list(map(int, Popen(["factor", str(n)], stdout=PIPE).communicate()[0].split()[1:]))


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 a(n):
    if n == 1:
        return 1
    f = fast_prime_factorization(2*n)
    f2 = [v ** len(list(gr)) for v, gr in groupby(f)]
    l = len(f2)
    ans = 1<<62
    for s in range(1<<l):
        p = 1
        q = 1
        for i in range(l):
            if s>>i & 1:
                p *= f2[i]
            else:
                q *= f2[i]
        if p==1 or q==1:
            continue
        g, x, y = egcd(-p, q)
        a = abs(y) * q
        
        if ans > a:
            ans = a
    return ans



print(a(N))

Solution (Python):

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)):
  if sum(pro)==0:
    continue
  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
  
  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)

Solution (Python):
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop



n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

def modinv(a, n):
    (x, lastx) = (0, 1); (y, lasty) = (1, 0); p = n
    while p != 0:
       q = a // p; (a, p) = (p, a % p)
       (x, lastx) = (lastx - q * x, x); (y, lasty) = (lasty - q * y, y)
    return lastx % n

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1: arr.append([temp, 1])
    if arr == []: arr.append([n, 1])
    return arr

N = n1()

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

fact = factorization(N)

if fact[0][0] == 2:
    fact[0][1] += 1
else:
    fact = [[2, 1]] + fact



ans = 10**16
for n in range(2**len(fact)-1):
    cand = bin(n)[2:].zfill(len(fact))
    k = 1
    q = 1

    for i in range(len(cand)):
        p, t = fact[i][0], fact[i][1]
        if cand[i] == "1":
            k *= p**t
        else:
            q *= p**t

    x = - modinv(k, q) % q
    tmp = k*x

    """
    if k % 2 == 0:
        if x % 2 != 0:
            x *= 2
    else:
        if x % 2 != 0:
            x *= 2
    """

    ans = min(tmp, ans)
    

ans = min(tmp, ans)

print(ans)

Solution (Python):
inpl = lambda: list(map(int,input().split()))
from math import sqrt, ceil, gcd
def divisors(n, sort=True, reverse=False):
    sqn = int(ceil(sqrt(n)))
    div_list = []
    if sqn*sqn == n:
        div_list.append(sqn)
    for i in range(1,sqn):
        if n % i == 0:
            div_list.append(i)
            div_list.append(n//i)
    if sort:
        div_list.sort(reverse=reverse)
    return div_list

def inv_mod(a, p=10**9+7):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0

N = int(input())
M = 2*N
divlist = divisors(M)
kmin = M-1
for p in divlist:
    q = M // p
    if p == 1 or q == 1 or gcd(p,q) > 1:
        continue
    else:
        m = q - inv_mod(p, q)
        k = p*m
        if k < kmin:
            kmin = k
print(kmin)

Solution (Python):
from itertools import product
def prime_factors(N): 
    ret = []
    middle = int( N**(1/2))
    tmp = N
    for i in range(2, middle+1):
        if tmp%i == 0:
            t = 1
            while tmp%i == 0:
                tmp //= i
                t *= i
            ret.append(t)
    if tmp != 1:
        ret.append(tmp)
    return ret

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 main():
    N = int( input())
    
    P = prime_factors(2*N)
    M = len(P)
    ans = 2*N-1
    
    for p in product( range(2), repeat=M):
        x = 1
        for i, t in enumerate(p):
            if t == 1:
                x *= P[i]
        y = N*2//x
        if x == 1:
            if y-1 < ans:
                ans = y-1
            continue
        if y == 1:
            if x-1 < ans:
                ans = x-1
            continue
        _, a, b = xgcd(x,y)
        now = -a*x
        
        if a < 0:
            pass
        else:
            now = -b*y
        if now < ans:
            ans = now
    print(ans)
        
        
if __name__ == '__main__':
    main()

Solution (Python):
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

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

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

data = []
for p in dic:
    data.append(p**dic[p])

n = len(data)
ans = 2*N
for i in range(2**n):
    A = 1
    B = 1
    for j in range(n):
        if i>>j & 1:
            A *= data[j]
        else:
            B *= data[j]

    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)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())



def gcd(a,b):
    if b == 0:
        return a, 1, 0
    s = a % b
    t = a // b
    d, x, y = gcd(b, s)
    x,y = y, x -  t * y
    if d < 0:
        d,x,y = -d,-x,-y
    return d, x, y 

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

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

M = 2*N
divs = divisors(M)

if len(divs) == 2:
    pass

ans = 10**20
for m1 in divs:
    m2 = M // m1 
    d,t1,t2 = gcd(-m1,m2)
    if d > 1:
        continue
    if t1 > 0:
        ans = min(ans, m1*t1)

print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

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

N = int(readline())
res = []
for i in range(1, N):
  if i*i > 8*N:
    break
  if (8*N)%i:
    continue
  res.append(i)
  res.append(8*N//i)


def sqrt(x):
    ok = 0
    ng = 10**18
    while (ng-ok) > 1:
        med = (ok+ng)//2
        if med*med <= x:
            ok = med
        else:
            ng = med
    return ok
    

M = 8*N

ans = 2*N-1
for r in res:
    if r == 1:
        continue
    u = M//r
    if u == 1 or u == 2:
        continue
    if gcd(r, u) > 2:
        continue
    gc, xx, yy = egcd(r, u)
    if gc == 1:
        xx *= 2
        yy *= 2
    xx *= -1
    yy *= -1
    xx %= u
    k = xx*r
    Ml = k*(k+2)
    j = (sqrt(1+Ml)-1)//2
    ans = min(ans, j)
print(ans)

Solution (Python):
import typing
def _inv_gcd(a: int, b: int) -> typing.Tuple[int, int]:
    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 base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
n=int(input())*2
ans=n-1
i=2
factors=[]
while i*i<=n:
  if n%i==0:
    tmp=1
    while n%i==0:
      n=n//i
      tmp=tmp*i
    factors.append(tmp)
  else:
    i+=1
if n!=1:
  factors.append(n)
for i in range(2**len(factors)):
  s=base10toN(i,2)
  slist=[]
  for j in s:
    slist.append(j)
  slist.reverse()
  for j in range(len(factors)-len(s)):
    slist.append('0')
  left=1
  right=1
  for j in range(len(factors)):
    if slist[j]=='0':
      left=left*factors[j]
    else:
      right=right*factors[j]
  if left*_inv_gcd(left,right)[1]>1:
    ans=min(ans,left*_inv_gcd(left,right)[1]-1)
print(ans)

Solution (Python):
from functools import lru_cache 






def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def is_prime(n):
    "Miller Rabin primality test. 2 <= n <= 2 ** 64 is required"
    if n % 2 == 0:
        return n == 2
    d = n - 1
    r = (d & -d).bit_length() - 1
    d >>= r

    
    if n < 2152302898747:
        if n < 9080191:
            if n < 2047:
                witnesses = [2]
            else:
                witnesses = [31, 73]
        else:
            if n < 4759123141:
                witnesses = [2, 7, 61]
            else:
                witnesses = [2, 3, 5, 7, 11]
    else:
        if n < 341550071728321:
            if n < 3474749660383:
                witnesses = [2, 3, 5, 7, 11, 13]
            else:
                witnesses = [2, 3, 5, 7, 11, 13, 17]
        else:
            if n < 3825123056546413051:
                witnesses = [2, 3, 5, 7, 11, 13, 17, 19]
            else:
                witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
    

    for a in witnesses:
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x *= x
            x %= n
            if x == n - 1:
                break
        else:
            return False
    return True


@lru_cache() 
def find_factor(n):
    "Find a non-trivial factor of n by using Pollard's rho algorithm."
    m = int(n ** 0.125) + 1
    c = 1
    while True:
        y = 1
        r = 1
        q = 1
        g = 1
        while g == 1:
            x = y
            for _ in range(r):
                y = (y * y + c) % n
            for k in range(0, r, m):
                ys = y
                for _ in range(m):
                    y = (y * y + c) % n
                    q = q * (x - y) % n
                g = gcd(q, n)
                if g != 1:
                    break
            else:  
                ys = y
                for _ in range(r-k):
                    y = (y * y + c) % n
                    q = q * (x - y) % n
                g = gcd(q, n)
            r *= 2

        if g == n:
            g = 1
            while g == 1:
                ys = (ys * ys + c) % n
                g = gcd(x - ys, n)

        if g == n:
            c += 1  
        else:  
            return g


prime_numbers_200 = [
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
    41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 
    89, 97, 101, 103, 107, 109, 113, 127, 131, 
    137, 139, 149, 151, 157, 163, 167, 173, 179, 
    181, 191, 193, 197, 199
]

def fac(n, try_small_factor = True):
    """
    引数 n の素因数分解をして、素因数を昇順に格納したリストを返す。
    ex. fac_small(60) == [2, 2, 3, 5]
    計算量は O(n ^ 1/4) 程度。
    """
    if n == 1:
        return []
    if is_prime(n):
        return [n]

    ret = []
    if try_small_factor:
        for p in prime_numbers_200:
            while n % p == 0:
                ret.append(p)
                n //= p
            if n == 1:
                return ret

    while n != 1 and not is_prime(n):
        f = find_factor(n)
        if is_prime(f):
            while n % f == 0:
                ret.append(f)
                n //= f
        elif is_prime(n // f):
            ret.append(n // f)
            n = f
        else:
            return sorted(ret + fac(f, False) + fac(n // f, False))

    if n == 1:
        return sorted(ret)
    else:
        ret.append(n)
        return sorted(ret)


N = int(input())
if N == 1:
    print(1)
    exit()
N *= 2
factors = fac(N)
rps = []
index = 0
while index < len(factors):
    f = factors[index]
    tmp = f
    index += 1
    while index < len(factors) and factors[index] == f:
        tmp *= f
        index += 1
    rps.append(tmp)

k = 10 ** 18

b = len(rps)
for i in range(1 << b):
    x = 1
    for j in range(b):
        if i & (1 << j):
            x *= rps[j]
    y = N // x
    m = pow(x, -1, y)

    n = (m * x + 1) // y
    if m == 0 or n == 0:
        m += y
        n += x
    k = min(m * x, k)
    if k * (k - 1) % N == 0:
        k -= 1
    
    
print(k)

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    def PrimeDecomposition(N):
        ret = {}
        n = int(N ** 0.5)
        for d in range(2, n + 1):
            while N % d == 0:
                if d not in ret:
                    ret[d] = 1
                else:
                    ret[d] += 1
                N //= d
            if N == 1:
                break
        if N != 1:
            ret[N] = 1
        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

    N = int(input())
    if N == 1:
        print(1)
        exit()
    P = PrimeDecomposition(N)
    if 2 in P:
        P[2] += 1
    else:
        P[2] = 1
    p_list = list(P.keys())
    np = len(p_list)
    ans = 2*N
    for i in range(2 ** np):
        p1 = 1
        p2 = 1
        for j in range(np):
            pp = p_list[j]
            if i >> j & 1:
                p1 *= pp ** P[pp]
            else:
                p2 *= pp ** P[pp]
        _, s2, s1 = extgcd(p2, p1)
        while s1 >= 0 or s2 <= 0:
            s1 -= p2
            s2 += p1
        while s2 - p1 > 0 and s1 + p2 < 0:
            s2 -= p1
            s1 += p2
        ans = min(ans, (-s1)*p1)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from math import *

def inv(a, m) : 
	
	m0 = m 
	x0 = 0
	x1 = 1

	if (m == 1) : 
		return 0

	
	while (a > 1) : 
		
		q = a // m 

		t = m 

		
		
		m = a % m 
		a = t 

		t = x0 

		x0 = x1 - q * x0 

		x1 = t 
	
	
	if (x1 < 0) : 
		x1 = x1 + m0 

	return x1 

def findMinX(num, rem, k) : 
	
	
	prod = 1
	for i in range(0, k) : 
		prod = prod * num[i] 

	
	result = 0

	
	for i in range(0,k): 
		pp = prod // num[i] 
		result = result + rem[i] * inv(pp, num[i]) * pp 
	
	
	return result % prod 

n = int(input())

ans = 1e18
m = 2*n
i = 1
while(i <= m):
	if(n == i):
		print(i*2 - 1)
		exit(0)
	i *= 2

i = 2
while(i*i <= m):
	if(m % i == 0):
		if(gcd(i, m // i) == 1):
			num = [0, 0]
			rem = [0, 0]
			num[0] = i
			num[1] = m // i
			rem[0] = 0
			rem[1] = m // i - 1
			ans = min(ans, findMinX(num, rem, 2))
			num[0] = m // i
			num[1] = i
			rem[0] = 0
			rem[1] = i - 1
			ans = min(ans, findMinX(num, rem, 2))
	i += 1

print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
def factor(n, m=None):
    
    arr = {}
    temp = n
    M = int(-(-n**0.5//1))+1
    if m is not None:
        M = min(m+1, M)
    for i in range(2, M):
        if i>temp:
            break
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if not arr:
        arr[n] = 1

    return arr
n *= 2
f = factor(n)

from itertools import product
ans = n-1
def gcd2(a, b):
    """a*x + b*y = gcd(a,b)なるx,yも求める
    """
    l = []
    while b:
        l.append(divmod(a,b))
        a, b = b, a%b
    x, y = 1, 0
    for aa,bb in l[::-1]:
        x, y = y, x - aa*y
    return a, x, y
def sub(x,y):
    g,k,l = gcd2(x, -y)
    if g!=1:
        return None
    return abs(k*x)
for ks in product(*[range(2) for _ in f.values()]):
    val = 1
    val2 = 1
    for k,v in zip(ks, f.keys()):
        if k:
            val *= pow(v,f[v])
        else:
            val2 *= pow(v,f[v])

    if val==1 or val2==1:
        continue
    res = gcd2(val, -val2)
    if res is not None and abs(res[0])==1:

        ans = min(ans, abs(val*res[1]))
print(ans)