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


# from nagiss-san's AC
def fast_prime_factorization(n):
    # 素因数分解（ロー法）  O(n^(1/4) polylog(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
    # print(factorization)
    factor_list = []
    for k in factorization.keys():
        factor_list.append(k ** factorization[k])

    # trivial answer
    res = 2 * n - 1

    # power set
    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))
        # 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()

Submission status: Accepted

Solution code:
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
#print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
#print(l)
d=deque()
d.append([])

for i in range(len(l)):
    x=list(range(values[i]+1))
    d2 = deque()
    #print(x)
    while len(d)>0:
        l=d.popleft()
        for j in x:
            l2=l[:]
            l2.append(j)
            d2.append(l2)
    d=d2
    #print(d)
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])
    #print(num,res)
    #x*num=k+1のときを考える
    if ggcd(num,res)==1:
        #x*num+y*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)

Submission status: Accepted

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


# V = [(X_i, Y_i), ...]: X_i (mod Y_i)
def remainder(V):
    x = 0; d = 1
    for X, Y in V:
        g, a, b = 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  # nがiで何回割り切れるか
            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

# prime_fac = 2*N の素因数分解
# 2*N|k*(k+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)

Submission status: Accepted

Solution code:
from collections import Counter


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


def chineseRem(b1, m1, b2, m2):
    # 中国剰余定理
    # x ≡ b1 (mod m1) ∧ x ≡ b2 (mod m2) <=> x ≡ r (mod m)
    # となる(r. m)を返す
    # 解無しのとき(0, -1)
    d, p, q = egcd(m1, m2)
    if (b2 - b1) % d != 0:
        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


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)

Submission status: Accepted

Solution code:
# gcdと逆元
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)

Submission status: Accepted

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

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

# 拡張ユークリッドの互除法.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:
from itertools import groupby

N = int(input())
def fast_prime_factorization(n):
    # 素因数分解（ロー法）  O(n^(1/4) polylog(n))
    from subprocess import Popen, PIPE
    return list(map(int, Popen(["factor", str(n)], stdout=PIPE).communicate()[0].split()[1:]))


def egcd(a, b):
    # 拡張ユークリッド互除法
    # ax + by = gcd(a,b)の最小整数解を返す
    # 最大公約数はg
    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
        #print(p, q, x, y, a)
        if ans > a:
            ans = a
    return ans

#print(a(15**12))

print(a(N))

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

Submission status: Accepted

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

# sys.setrecursionlimit(5000)

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

#print(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)
    #print(ans, k, x, q, k*x)

ans = min(tmp, ans)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import product
def prime_factors(N): #素因数 1を含まないことに注意
    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())
    # print("start")
    P = prime_factors(2*N)
    M = len(P)
    ans = 2*N-1
    # print(M)
    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
        # print(x, y, a, b)
        if a < 0:
            pass
        else:
            now = -b*y
        if now < ans:
            ans = now
    print(ans)
        
        
if __name__ == '__main__':
    main()

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

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)

Submission status: Accepted

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

# ax + by = d
# d,x,y
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)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

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

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

    return (s, m0)
def 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)

Submission status: Accepted

Solution code:
from functools import lru_cache # お好みで。あると同じ素因数分解をするときに楽できる。

# 参考1: https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98
# 参考2: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
# 参考3: https://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%A9%E3%83%BC%E3%83%89%E3%83%BB%E3%83%AD%E3%83%BC%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E6%B3%95


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

    # witnesses をいい感じに決める。
    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]
    # witnesses の決定終了

    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:  # 残りの k から r までをやる
                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  # c を変えて続行。
        else:  # g は n の非自明な素因数。
            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(x, y, m * x)
    
print(k)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import *

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

	if (m == 1) : 
		return 0

	# Apply extended Euclid Algorithm 
	while (a > 1) : 
		# q is quotient 
		q = a // m 

		t = m 

		# m is remainder now, process 
		# same as euclid's algo 
		m = a % m 
		a = t 

		t = x0 

		x0 = x1 - q * x0 

		x1 = t 
	
	# Make x1 positive 
	if (x1 < 0) : 
		x1 = x1 + m0 

	return x1 

def findMinX(num, rem, k) : 
	
	# Compute product of all numbers 
	prod = 1
	for i in range(0, k) : 
		prod = prod * num[i] 

	# Initialize result 
	result = 0

	# Apply above formula 
	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)

Submission status: Accepted

Solution code:
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):
    # mを与えると、高々その素因数まで見て、残りは分解せずにそのまま出力する
    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)
# print(f)
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])
#     print(val*val2)
    if val==1 or val2==1:
        continue
    res = gcd2(val, -val2)
    if res is not None and abs(res[0])==1:
#         print(val,val2,res)
        ans = min(ans, abs(val*res[1]))
print(ans)