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

l=len(a)
if l==1:
  if a[0][0]==2:
    print(2*n-1)
    exit()
  else:
    print(n-1)


step=0
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:
import os
import sys

import numpy as np


def solve(inp):
    def _inv_gcd(a, b):
        a %= b
        if a == 0:
            return (b, 0)

        s = b
        t = a
        m0 = 0
        m1 = 1

        while t:
            u = s // t
            s -= t * u
            m0 -= m1 * u  # |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, m):

        n = len(r)

        # Contracts: 0 <= r0 < m0
        r0 = 0
        m0 = 1
        for i in range(n):
            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)

    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

    # print(prime_factorize(1100144))

    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

        r = np.array([0, 1])
        m = np.array([b, a])
        y, z = crt(r, m)
        if y == 0 and z > 0:
            y += z
        y -= 1
        if y > 0:
            ver = y * (y + 1) // 2
            if ver//n*n==ver:
                ans = min(ans, y)

    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:
import os
import sys

import numpy as np


def solve(inp):
    def _inv_gcd(a, b):
        a %= b
        if a == 0:
            return (b, 0)

        s = b
        t = a
        m0 = 0
        m1 = 1

        while t:
            u = s // t
            s -= t * u
            m0 -= m1 * u  # |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, m):

        n = len(r)

        # Contracts: 0 <= r0 < m0
        r0 = 0
        m0 = 1
        for i in range(n):
            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)

    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

    print(prime_factorize(1100144))

    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

        r = np.array([0, 1])
        m = np.array([b, a])
        y, z = crt(r, m)
        if y == 0 and z > 0:
            y += z
        y -= 1
        if y > 0:
            ver = y * (y + 1) // 2
            if ver//n*n==ver:
                ans = min(ans, y)

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

  a=np.array(factor)
  print(a)
  ui, counts = np.unique(a, return_counts=True)
  
  for i in range(ui.size):
    cts=counts[i]
    if cts>1:
      div=ui[i]**(cts//2)
      num=num//div
      counts[i]=cts%2
  n=num
  for uii in ui:
    if n % uii ==0:
      if ((n/uii)-1) %uii==0:
        num=num//uii
  min=num-1
  num=n
  for uii in ui:
    if n % uii ==0:
      if ((n/uii)+1) %uii==0:
        num=num//uii
  min2=num
 
  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()

Submission status: Wrong Answer

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
N *= 2

for k in range(2, N+1):
	if k*(k+1) % N == 0:
		print(k)
		exit()

Submission status: Wrong Answer

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)

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: 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
    b = (-1-sq)/2
    if a > 0 and a.is_integer():
        ans = min(ans,a)
    if b > 0 and b.is_integer():
        ans = min(ans,b)
    if ans != float('inf'):
        print(int(ans))
        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):
			print("yes")
			ans=b*k
		k=k+1
	i=i+1	
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

import sys
import math

N = int(sys.stdin.readline())

a = 1
while True:
    x = 8 * a * N + 1
    t = math.floor(math.sqrt(x))
    if x == t ** 2:
        if (t + 1) % 2 == 0:
            break
    a += 1

print(int((t + 1) // 2))

Submission status: Wrong Answer

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

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,cand2)
        if (cand2*(cand2+1))%(2*N)==0:
            out = min(out,cand2)

print(out)

Submission status: Wrong Answer

Solution code:
N = int(input())

#n>1における素因数分解のアルゴリズム
#素因数をそのまま羅列
def prime_factorize(n):
    ls = []
    while n % 2 == 0:
        ls.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            ls.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        ls.append(n)
    return ls
print(prime_factorize(N))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import chain, combinations


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 solve(n):
    if n == 1:
        return 1
    # sieve
    primes = []
    primes_array = [1] * (10 ** 6)
    primes_array[0] = 0
    primes_array[1] = 0
    for p in range(10 ** 6):
        if primes_array[p] == 1:
            primes.append(p)
            for q in range(p * p, 10 ** 6, p):
                primes_array[q] = 0
    # print(primes)
    # prime factorization
    factorization = defaultdict(int)
    m = 2 * n
    for p in primes:
        while m % p == 0:
            m = m // p
            factorization[p] += 1
    if m > 1:
        for p in range(10 ** 6, 32 * 10 ** 6):
            if m % p == 0:
                q = m // p
                if p > 1:
                    factorization[p] += 1
                if q > 1:
                    factorization[q] += 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 = 1
        for r in s:
            p *= r
        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:
# 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 *= 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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


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

INF = 1 << 60


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


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

    b = Bisect(f)

    for i in range(1, 100000):
        t = K*i
        j = b.bisect_left(t, 0, 10**9)
        if f(j) == t:
            return j


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 *= key * p[key]
    i >>= 1
    cnt += 1
  y = N // x
  iv = inv_gcd(x, y)[1]
  ans = min(ans, iv * x - 1)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import chain, combinations


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 solve(n):
    # sieve
    primes = []
    primes_array = [1] * (10 ** 6)
    primes_array[0] = 0
    primes_array[1] = 0
    for p in range(10 ** 6):
        if primes_array[p] == 1:
            primes.append(p)
            for q in range(p * p, 10 ** 6, p):
                primes_array[q] = 0
    # print(primes)
    # prime factorization
    factorization = defaultdict(int)
    m = 2 * n
    for p in primes:
        while m % p == 0:
            m = m // p
            factorization[p] += 1
    if m > 1:
        for p in range(10 ** 6, 32 * 10 ** 6):
            if m % p == 0:
                q = m // p
                if p > 1:
                    factorization[p] += 1
                if q > 1:
                    factorization[q] += 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 = 1
        for r in s:
            p *= r
        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 math

N=int(input())

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

    FACT=dict()

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

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

    return FACT

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

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

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

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

Solution code:
N = int(input())

def K(m):
    return (1 + 8 * N * m) ** 0.5

m = 1
while (- 1 + K(m)) % 2 != 0:    
    m += 1

k = int((- 1 + K(m)) / 2)
print(k)

Submission status: Wrong Answer

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):
  x = 1
  cnt = 0
  while i:
    if i & 1:
      key = L[cnt]
      x *= key * p[key]
    i >>= 1
    cnt += 1
  y = N // x
  if y < x:
    if x % y == 1:
      ans = min(ans, x - 1)
    continue
  iv = inv_gcd(x, y)[1]
  ans = min(ans, iv * x - 1)

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

# print(10**15)

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:
import numpy as np
import math
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 = int(input())

if len(factorization(N)) == 1:
    max_prime = 1
else:
    max_prime = factorization(N)[-1][0]
k = max_prime

while True:
    if k != 1 and (int((1 / 2) * k * (k + 1)) % N == 0 or int((1 / 2) * k * (k - 1)) % N == 0):
        print(k)
        break
    k += max_prime

Submission status: Wrong Answer

Solution code:
n=int(input())


for i in range(int(n**.5)+1,1,-1):
    if n % i ==0:
        for j in range ( i, n + 1 ):
            if (((j * (j + 1))) % (2 * n)) == 0:
                print ( j )
                exit(0)
else:print(n-1)

Submission status: Wrong Answer

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

ans = N - 1
p = prime(N * 2)

L = []
for key in p.keys():
  L.append(key)

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

print(ans)

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)):
  if sum(pro)==0:
    continue
  prod = 1
  for i,p in enumerate(pro):
    if p==1:
      prod *= lis[i]
  q = prod
  while q<N and q<ans:
    if q * (q-1) % (2*N) == 0:
      ans = min(ans,q)
      break
    if q * (q+1) % (2*N) == 0:
      ans = min(ans,q)
      break
    q += prod
print(ans)