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

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

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


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

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

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

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

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

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

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

"""
def main():

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

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


    #約数列挙
    #10^6以下で約数の数が最大なのは720720の時(240個しかない！)
    def divisors(N):
        pf = primeFactor(N)
        ret = [1]
        for p in pf:
            ret_prev = ret
            ret = []
            for i in range(pf[p]+1):
                for r in ret_prev:
                    ret.append(r * (p ** i))
        return sorted(ret)
    
    #拡張ユークリッド
    def egcd(a, b):
        if a == 0:
            return b, 0, 1
        else:
            g, y, x = egcd(b % a, a)
            return g, x - (b // a) * y, y



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


main()

Submission status: Wrong Answer

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


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


# print(divisors(z))

z=int(input())


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

print(ans if z-1 else 1)

Submission status: Wrong Answer

Solution code:
n=int(input())

j=int(-3+pow(9-8*(1-n),1/2)/2)


for i in range(j,n):
  s=i*(i+1)/2
  if s%n==0:
    ans=i
    break
print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd

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

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

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

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

    x0,y0 = euclid(A,B)

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

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

    limit = max(limit1,limit2)

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

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

    x0,y0 = euclid(A,B)

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

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

    limit = max(limit1,limit2)

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

print(ans)

Submission status: Wrong Answer

Solution code:
z=int(input())

def solv_quadratic_equation(a, b, c):
  #  2次方程式を解く 
  D = (b**2 - 4*a*c) ** (1/2)
  x_1 = (-b + D) / (2 * a)
  x_2 = (-b - D) / (2 * a)

  return x_1,x_2

ans=0

i=1

while True:

  a,b=solv_quadratic_equation(1,1,-2*(z*i))

  if a>b:
    if a.is_integer():
      # print(a)
      # print(b)
      ans=a
      break
  elif a<b:
    if b.is_integer():
      # print(a)
      # print(b)
      ans=b
      break

  i+=1

print(int(ans))

Submission status: Wrong Answer

Solution code:
z=int(input())

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


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


print(divisors(z))

# for n in range(1,10):
#   # (変数) = (条件がTrueのときの値) if (条件) else (条件がFalseのときの値)
#   ans = n-1 if n%2 else 2*n-1
#   print(ans)

#print(chinese_remainder([2, 3, 2], [3, 5, 7]))

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

print(ans if z-1 else 1)

Submission status: Wrong Answer

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


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


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


divs = list_divs(N)

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

Submission status: Wrong Answer

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

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

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

from math import gcd
def resolve():
    n = int(input())
    ans = 2 * n - 1
    if n * (n + 1) // (2 * n):
        ans = min(ans, n)
    if (n - 1) * n // (2 * n):
        ans = min(ans, n - 1)

    n *= 2
    for d in range(2, int(n**.5) + 1):
        if n % d:
            continue
        x, y = d, n // d
        if gcd(x, y) > 1:
            continue
        # x の mod y での inv
        a = modinv(x, y)
        ans = min(ans, a * x - 1)
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

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

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

from math import gcd
def resolve():
    n = int(input())
    ans = 2 * n - 1
    if n * (n + 1) // (2 * n):
        ans = min(ans, n)
    if (n - 1) * n // (2 * n):
        ans = min(ans, n - 1)

    for d in range(2, int((2 * n)**.5) + 1):
        if n % d:
            continue
        x, y = d, n // d
        if gcd(x, y) > 1:
            continue
        # x の mod y での inv
        a = modinv(x, y)
        ans = min(ans, a * x - 1)
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

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

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

from math import gcd
def resolve():
    n = int(input())
    ans = 2 * n - 1
    if n * (n + 1) // (2 * n):
        ans = min(ans, n)
    if (n - 1) * n // (2 * n):
        ans = min(ans, n - 1)

    for d in range(2, int(n**.5) + 1):
        if n % d:
            continue
        x, y = d, n // d
        if gcd(x, y) > 1:
            continue
        # x の mod y での inv
        a = modinv(x, y)
        ans = min(ans, a * x - 1)
    print(ans)
resolve()

Submission status: Wrong Answer

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 crt(r: typing.List[int], m: typing.List[int]) -> typing.Tuple[int, int]:
    assert len(r) == len(m)

    n = len(r)

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

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

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

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

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

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

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

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

    return (r0, m0)

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
z=int(input())

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



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

#print(divisors(2*z))

# for n in range(1,10):
#   # (変数) = (条件がTrueのときの値) if (条件) else (条件がFalseのときの値)
#   ans = n-1 if n%2 else 2*n-1
#   print(ans)

#print(chinese_remainder([2, 3, 2], [3, 5, 7]))

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

#print(ans if z-1 else 1)

Submission status: Wrong Answer

Solution code:
s = 0
n = int(input())
for i in range(1,n):
	s += i
	if(s%n == 0):
		print(i)
		exit()

Submission status: Wrong Answer

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

Solution code:
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    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 _ in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for _ in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

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

if __name__ == "__main__":
    N = int(input())
    if N==1:
        print(1)
        exit()

    pf = primeFactor(N)
    # print(pf)
    div = [1]
    for p,e in pf.items():
        tmp = []
        for i in range(1,e+1):
            tmp += [x*pow(p,i) for x in div]
        div += tmp
    div.sort()
    for x in div:
        if x==1: continue
        k = x - 1
        s = k*(k+1)//2
        if s%N==0:
            print(k)
            exit()
        k = x
        s = k*(k+1)//2
        if s%N==0:
            print(k)
            exit()
        # print(x)

Submission status: Wrong Answer

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

def yakusu(n):
    a = []
    for i in range(1, int(math.sqrt(2*n))+2):
        if(2*n % i == 0):
            a.append(i)
    return a

def exgcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = exgcd(b % a, a)
        return g, x - (b // a) * y, y
    
def CRT(b1, m1, b2, m2):
    # 中国剰余定理
    # x ≡ b1 (mod m1) ∧ x ≡ b2 (mod m2) <=> x ≡ r (mod m)
    # となる(r. m)を返す
    # 解無しのとき(0, -1)
    d, p, q = exgcd(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
x = yakusu(n)
a = 1e16
for i in range(len(x)):
    r, m = CRT(-1, 2*n//x[i], 0, x[i])
    if(r > 0):
        a = min(a, r)
print(a)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = 0
for i in range(1,n):
  if (x+i)%n == 0:
    print(i)
    break

Submission status: Wrong Answer

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

    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
        # print(a, b, m, k)

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

Submission status: Wrong Answer

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    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

    n = inp[0]
    pf = prime_factorize(n)
    l = len(pf)
    pfk = np.zeros(l, np.int64)
    for i, p in enumerate(pf):
        pfk[i] = 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
        # print(a, b, m, k)

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

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

Submission status: Wrong Answer

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):
    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 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
    if n % 2 == 1:
        res = n - 1
    else:
        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))
            # print(p, q, abs(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: Wrong Answer

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    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

    n = inp[0]
    pf = prime_factorize(n)
    l = len(pf)
    pfk = np.zeros(l, np.int64)
    for i, p in enumerate(pf):
        pfk[i] = p ** pf[p]

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

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

        m = mod_inv(b, a)
        k = b * m - 1
        # print(a, b, m, k)

        verify = k * (k + 1) // 2
        if verify // n * n == verify:
            ans = min(ans, k)

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:
  print(1)
  exit()
  
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

a=factorization(n)
step=0

for i,j in a:
  step=max(step,i**j)
exit()

for m in range(step,2*n,step):
  if (m*(m-1)//2)%n==0:
    print(m-1)
    exit()
  if (m*(m+1)//2)%n==0:
    print(m)
    exit()

Submission status: Wrong Answer

Solution code:
n=int(input())
if n==1:
  print(1)
  exit()
  
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

a=factorization(n)
step=0
exit()
for i,j in a:
  step=max(step,i**j)

for m in range(step,2*n,step):
  if (m*(m-1)//2)%n==0:
    print(m-1)
    exit()
  if (m*(m+1)//2)%n==0:
    print(m)
    exit()

Submission status: Wrong Answer

Solution code:
n=int(input())
for i in range(int((2*n)**.5),n):
    # print(i*(i+1),2*n)
    if (i*(i+1)//2) % n == 0:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
n=int(input())
for i in range(int((2*n)**.5),n):
    # print(i*(i+1),2*n)
    if i*(i+1) % (2* n) == 0:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=int(n-1)
n=n*2
i=int(2)
primeofn=list()
while i**2 <= n:
	if n%i == 0:
		primeofn.append(i)
		n=int(n/i)
	else:
		i=i+1
primeofn.append(n)

trueprimeofn=list()
while len(primeofn) > 0:
	a=primeofn[0]
	b=primeofn.count(a)
	trueprimeofn.append(a**b)
	for i in range(b):	
		primeofn.remove(a)

i=int(0)
while i < 2**len(trueprimeofn):
	h=i
	j=int(0)
	b=int(1)
	c=int(1)
	while j < len(trueprimeofn):
		if  h%2== 0:
			b=b*trueprimeofn[j]
			h=h/2
			
		else:
			c=c*trueprimeofn[j]
			h=(h-1)/2
		j=j+1
	k=int(1)
	while (b*k < ans) and (k<c):
		if ((b*k+1)%c == 0) and (ans > b*k):
			ans=b*k
		k=k+1
	i=i+1	
print(ans)

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

n = inp()
delta = 8*n
t = 1
from math import sqrt
ans = float('inf')
while True:
    t += delta
    sq = sqrt(t)
    a = (-1+sq)/2
    if a > 0 and a.is_integer():
        ans = min(ans,a)
    if ans != float('inf'):
        print(int(ans))
        break

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
def factorization(num):

    return factor
def main():
  n2=int(input())
  n=n2
  if n==1:
    print(1)
    exit()
  num=n
  factor = []
  while num > 1:
    for i in range(num - 1):
      k = i + 2
      if num % k == 0:
        factor.append(k)
        num = int(num / k)
        break
  if len(factor)==1:
    print(n-1)
    exit()
  num=n

 
  list2 = []
  for i in range(1,len(factor)+1):
    iter = itertools.combinations(factor,i)
    list2.append(list(iter))
  for all in list2:
    for item in all:
      ji=1
      for cs in item:
        ji=ji*cs
      if((ji*(ji-1))//2)%n2==0:
        print(ji-1)
        exit()
      if((ji*(ji+1))//2)%n2==0:
        print(ji)
        exit()
main()