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())
nums = [int(1*i) for i in range(1,n)]
totalnums = []

for i in range(1,len(nums)+1):              # 累積和配列の作成
      totalnums.append(sum(nums[0:i]))

for i in range(len(totalnums)):
      if totalnums[i]%n == 0:
            print(nums[i])
            break

Submission status: Wrong Answer

Solution code:
n = int(input())
nums = [int(1*i) for i in range(1,n)]
totalnums = []

for i in range(1,len(nums)+1):              # 累積和配列の作成
      totalnums.append(sum(nums[0:i]))

for i in range(len(totalnums)):
      if totalnums[i]%n == 0:
            print("complete:",end="")
            print(nums[i])
            break

Submission status: Wrong Answer

Solution code:
from math import *
N=int(input())
"""
l=[]
pf={}
m=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
print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
print(l)
"""
a=1
while True:
    t=sqrt(1+8*a*N)
    if (pow(int(sqrt(1+8*a*N)),2)%(1+8*a*N)==0)and(int(t)%2==1):
        print((-1+int(t))//2)
        break
    a=a+1

Submission status: Wrong Answer

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

N = int(input())
a = 2
while True:
    target = a*N
    k1,k2 = solv_quadratic_equation(1,1,-target)
    k = max(k1,k2)
    if k == int(k):
        print(int(k))
        break
    a += 2

Submission status: Wrong Answer

Solution code:
N = int(input())

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

m = 1

while K(m).is_integer() == False:
    m += 1

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

Submission status: Wrong Answer

Solution code:
N = int(input())
# b**2 + b - 2aN = 0
# b = ()
for a in range(1,10**15):
    # print((-1 + (1 + 4 * 1 * 2*a*N)**0.5) / 2, (-1 - (1 + 4 * 1 * 2*a*N)**0.5) / 2)
    n = (-1 + (1 + 4 * 1 * 2*a*N)**0.5) / 2
    if n.is_integer():
        print(int(n))
        break

Submission status: Wrong Answer

Solution code:
a=int(input())


sum=0

for i in range(1,a):
  sum+=i
  if sum%a==0:
    print(i)
    break

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
ttl = 0
i  = 2

while True:
    ttl = i*(i+1)/2
    if ttl % N ==0:
        print(i)
        exit()
    i+=1

Submission status: Wrong Answer

Solution code:
from math import sqrt

n = int(input())

k_sum = 0
for i in range(1, n):
    k_sum += i
    if k_sum % n == 0:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
from math import *
N=int(input())
"""
l=[]
pf={}
m=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
print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
print(l)
"""
a=1
while True:
    t=sqrt(1+8*a*N)
    if (t.is_integer()==True)and(int(t)%2==1):
        print((-1+int(t))//2)
        break
    a=a+1

Submission status: Wrong Answer

Solution code:
a=int(input())


sum=0

for i in range(1,a):
  sum+=i
  if sum%a==0:
    print(sum)
    break

Submission status: Wrong Answer

Solution code:
n = int(input())
i = 2
m =n 
while True:
  vl = (((m*8+1)**0.5)-1)/2
  if vl == int(vl):
    print(int(vl))
    break
  m = n * i
  i+=1

Submission status: Wrong Answer

Solution code:
n=int(input())
i=1
while True:
  g=(i*(i+1))/2
  if g%11==0:
    print(i)
    break
  else:
    i=i+1

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    csum = 0
    for i in range(1,N):
        csum += i
        if((csum % N) == 0):
            print(i)
            return(0)
main()

Submission status: Wrong Answer

Solution code:
import math
N = int(input(""))
a = 0
for k in range(1,N):
  if ((k*k+k)/2)%N == 0:
    a += 1
    print(k)
    break
if a == 0:
  print(N-1)

Submission status: Wrong Answer

Solution code:
N = int(input())

m = 1
K = (1 + 8 * N * m) ** 0.5
while K.is_integer() == False:
    m += 1
    K = (1 + 8 * N * m) ** 0.5

print(int((- 1 + K) / 2))

Submission status: Wrong Answer

Solution code:
n=int(input())
#k*(k+1)//2
if n==1:ans=1
elif n%2:ans=n-1
else:ans=n*2
print(ans)

Submission status: Wrong Answer

Solution code:
def sum(k):
    result = 0
    for i in range(k+1):
        result += i
    return result
N = int(input("N"))
cont = True
_n = 0
while(cont):
    _n += 1
    if(int(sum(_n)/N) == sum(_n)/N):
        print(_n)
        cont = False

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def crt(rs,ms):
    def _inv_gcd(a,b):
        if a==0: return (b,0)
        s,t,m0,m1 = b,a,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)
    assert len(rs) == len(ms)
    n = len(rs)
    r0,m0 = 0,1
    for i in range(n):
        assert 1 <= ms[i]
        r1,m1 = rs[i] % ms[i], ms[i]
        if m0 < m1:
            r0,r1,m0,m1 = r1,r0,m1,m0
        if m0 % m1 == 0:
            if r0 % m1 != r1: return (0,0)
            continue
        g,im = _inv_gcd(m0,m1)
        u1 = m1 // g
        if (r1-r0) % g: return (0,0)
        x = (r1-r0) // g % u1 * im % u1
        r0 += x * m0
        m0 *= u1
        if r0 < 0: r0 += m0
    return (r0,m0)

divs = set()
m = 1
NN = 2*N
while m*m <= NN:
    if NN%m == 0:
        divs.add(m)
        divs.add(NN//m)
    m += 1

ans = NN-1
for x in divs:
    y = NN//x
    if y==1: continue
    r,m = crt([0,-1], [x,y])
    if r==m==0: continue
    ans = min(ans, r)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

ans=0

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

Submission status: Time Limit Exceeded

Solution code:
def prime_factorize(n):
    i = 2
    res = {}
    while i * i <= n:
        if n % i != 0:
            i += 1
            continue
        res[i] = 0
        while n % i == 0:
            res[i] += 1
            n //= i
        i += 1
    if n != 1:
        res[n] = 1
    return res
 
 
def solve(n):
    n *= 2
    pf = prime_factorize(n)
    l = len(pf)
    pfk = []
    for i, p in enumerate(pf):
        pfk.append(p ** pf[p])
 
    ans = 10 ** 18
 
    for bit in range(1 << l):
        a = 1
        for d in range(l):
            if bit & (1 << d):
                a *= pfk[d]
        b = n // a
 
        if a == 1:
            k = n - 1
        elif b == 1:
            k = n
        else:
            m = pow(b,-1, a)
            k = b * m - 1
        ans = min(ans, k)
 
    return ans
 
 
n = int(input())
ans = solve(n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
 
 
def inv_gcd(a, b):
    a = (a + b) % b
    if a == 0:
        return (b, 0)
    s, t = b, a
    m0, m1 = 0, 1
 
    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u
 
        tmp = s
        s = t
        t = tmp
        tmp = m0
        m0 = m1
        m1 = tmp
    
    if m0 < 0:
        m0 += b // s
    return (s, m0)
 
 
def crt(r, m):
    n = len(r)
    r0, m0 = 0, 1
 
    for i in range(n):
        r1, m1 = (r[i] + m[i]) % m[i], m[i]
 
        if m0 < m1:
            m0, m1 = m1, m0
            r0, r1 = r1, r0
        
        if m0 % m1 == 0:
            if r0 % m1 != r1:
                return (0, 0)
            continue
        
        g, im = inv_gcd(m0, m1)
 
        u1 = m1 // g
        if (r1 - r0) % g:
            return (0, 0)
        
        x = (r1 - r0) // g % u1 * im % u1
 
        r0 += x * m0
        m0 *= u1
        if (r0 < 0):
            r0 += m0
        
    return (r0, m0)
 
 
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
 
 
def main():
    n = int(input())
    divisors = make_divisors(2 * n)
 
    ans = n-1 if n%2 else 2*n-1
    for x in divisors:
        y = n * 2 // x
        if y == 1:
            continue
        r = [0, y-1]
        m = [x, y]
        rem, mod = crt(r, m)
        if rem == mod == 0:
            continue
        ans = min(ans, rem)
 
    
    print(ans if n-1 else 1)
 
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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


def 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,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: Time Limit Exceeded

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


# 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: Time Limit Exceeded

Solution code:
def inv_gcd(a,b):
    a=a%b
    if a==0:
        return (b,0)
    s=b;t=a
    m0=0;m1=1
    while(t):
        u=s//t
        s-=t*u
        m0-=m1*u
        s,t=t,s
        m0,m1=m1,m0
    if m0<0:
        m0+=b//s
    return (s,m0)
def inv_mod(x,m):
    assert 1<=m
    z=inv_gcd(x,m)
    assert z[0]==1
    return z[1]
def crt(r,m):
    assert len(r)==len(m)
    n=len(r)
    r0=0;m0=1
    for i in range(n):
        assert 1<=m[i]
        r1=r[i]%m[i]
        m1=m[i]
        if m0<m1:
            r0,r1=r1,r0
            m0,m1=m1,m0
        if (m0%m1==0):
            if (r0%m1!=r1):
                return (0,0)
            continue
        g,im=inv_gcd(m0,m1)
        u1=m1//g
        if ((r1-r0)%g):
            return (0,0)
        x=(r1-r0)//g % u1*im%u1
        r0+=x*m0
        m0*=u1
        if r0<0:
            r0+=m0
    return (r0,m0)
N=int(input())
def divide(n):
    res=[]
    i=1
    while(i*i<=n):
        if n%i==0:
            res.append(i)
            if i*i!=n:
                res.append(n//i)
        i+=1
    return res
ans=2*N
for b in divide(2*N):
    c=(2*N)//b
    tmp=crt([0,c-1],[b,c])
    if tmp==(0,0):
        continue
    x=tmp[0]
    if x==0:
        x=tmp[1]
    ans=min(x,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
if n==1:
  print(1)
  exit()
import numpy as np
def calc_div(N):
  sq = int(N**.5 + 10)
  x = np.arange(1, sq)
  x = x[N % x == 0]
  x = np.concatenate((x, N // x))
  return np.unique(x)

n*=2
div=calc_div(n)
#print(d1,d2)
ans=float('inf')
for x in div:
  x=int(x)
  y=n//x
  if np.gcd(x,y)==1:
    xx,yy=x,y
    while abs(xx-yy)>1:
      d=abs(xx-yy)
      if xx>yy:yy+=max(y,y*(d//y))
      else:xx+=max(x,x*(d//x))
    ans=min(ans,xx,yy)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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)

n = int(input())
divisor_list = []
n *= 2
for x in range(2, int(n ** 0.5) + 1):
    if n % x == 0:
        divisor_list.append([x, n // x])
ans = n - 1
for m1, m2 in divisor_list:
    if math.gcd(m1, m2) != 1:
        continue
    p, q = gcd_ext(m1, m2)
    tmp = (-1 * m1 * p) % (m1 * m2)
    ans = min(tmp, ans)
    tmp = (-1 * m2 * q) % (m1 * m2)
    ans = min(tmp, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import typing

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
  
# https://github.com/not522/ac-library-python/blob/master/atcoder/math.py
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)

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)
  
N=int(input())
F = make_divisors(2*N)

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

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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):
  lower_divisors , upper_divisors = [], []
  i = 1
  while i*i <= n:
    if n % i == 0:
      lower_divisors.append(i)
      if i != n // i:
        upper_divisors.append(n//i)
    i += 1
  return lower_divisors + upper_divisors[::-1]

#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)
  if rem == mod == 0:
      continue
  ans = min(ans, rem)

print(ans if z-1 else 1)

Submission status: Time Limit Exceeded

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
#factorization(24) 
## [[2, 3], [3, 1]] 
##  24 = 2^3 * 3^1


ans=n-1 if n%2==1 else 2*n-1
ary=factorization(2*n)
k=len(ary)
for i in range(2**k):
  x,y=1,1
  for j in range(k):
    if (i>>j)&1:
      x*=pow(ary[j][0],ary[j][1])
    else:
      y*=pow(ary[j][0],ary[j][1])
  xx,yy=x,y
  while abs(xx-yy)>1:
    d=abs(xx-yy)
    if xx>yy:yy+=max(y,y*(d//y))
    else:xx+=max(x,x*(d//x))
  ans=min(ans,xx,yy)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
if n==1:
  print(1)
  exit()
def make_divisors(n):  
  d1=[]
  d2=[]
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      if i != n // i:
        if (n//i)%2==0 and i%2==0:continue
        d2.append(n//i)
        d1.append(i)
  # divisors.sort()
  return d1,d2
def gcd(a, b):
  while b:
    a, b = b, a%b
  return a

ans=n-1 if n%2==1 else 2*n-1
d1,d2=make_divisors(2*n)
#print(d1,d2)
for x,y in zip(d1,d2):
  if gcd(x,y)==1:
    xx,yy=x,y
    while abs(xx-yy)>1:
      d=abs(xx-yy)
      if xx>yy:yy+=max(y,y*(d//y))
      else:xx+=max(x,x*(d//x))
    ans=min(ans,xx,yy)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from math import sqrt

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

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

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

    prime = [2, 3]
    for i in range(5, int(sqrt(n_copy)) + 1, 2):
        for p in prime:
            if p * p > i:
                prime.append(i)
                break

            if i % p == 0:
                break

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

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

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

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

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

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

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

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

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

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

    prime = [2, 3]
    for i in range(5, 32 * (10**6), 2):
        for p in prime:
            if p * p > i:
                prime.append(i)
                break

            if i % p == 0:
                break

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

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

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

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

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

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

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

    print(ans)

main()

Submission status: Time Limit Exceeded

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]
  prod2 = (N*2)//prod1
  if prod1<prod2:
    prod1,prod2 = prod2,prod1
    # continue
  for i in range(1,prod2+1):
    # if prod1*i>ans:
      # break
    if (prod1*i-1)%prod2==0:
      ans = min(ans, prod1*i-1)
      break
    if (prod1*i+1)%prod2==0:
      ans = min(ans, prod1*i)
      break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, i, sum_ = int(input()), 1, 1
while True:
  if sum_ % n == 0:
    print(i)
    break
  i += 1
  sum_ += i

Submission status: Time Limit Exceeded

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)
    for i in range(len(a)):
        a.append(2*n // a[i])
    return sorted(list(set(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: Time Limit Exceeded

Solution code:
n, i = int(input()), 1
while True:
  if ((i*(i+1))/2) % n == 0:
    print(i)
    break

Submission status: Time Limit Exceeded

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


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


def solve(n):
    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 > 0 and k * (k + 1) // 2 % n == 0:
            ans = min(ans, k)
        else:
            ans = min(ans, k + n)

    return ans


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

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

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
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 = 3*N
for i in range(len(K)):
    a, b = K[i]
    p = copy.copy(b)
    while(True):
        if b > ans:
            break
        if (2*b-1) % a == 0:
            ans = min(ans, 2*b-1)
        elif (2*b+1) % a == 0:
            ans = min(ans, 2*b)
        if b % 2 == 1:
            if ((b - 1) // 2) % a == 0:
                ans = min(ans, b - 1)
            elif ((b + 1) // 2) % a == 0:
                ans = min(ans, b)
        b += p

if N == 1:
    print(1)
elif N == 2:
    print(3)
else:
    print(ans)

Submission status: Time Limit Exceeded

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


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: Time Limit Exceeded

Solution code:
import copy
N = 10**15
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 = 3*N
for i in range(len(K)):
    a, b = K[i]
    p = copy.copy(b)
    while(True):
        if b > ans:
            break
        if (2*b-1) % a == 0:
            ans = min(ans, 2*b-1)
        elif (2*b+1) % a == 0:
            ans = min(ans, 2*b)
        if b % 2 == 1:
            if ((b - 1) // 2) % a == 0:
                ans = min(ans, b - 1)
            elif ((b + 1) // 2) % a == 0:
                ans = min(ans, b)
        b += p

if N == 1:
    print(1)
elif N == 2:
    print(3)
else:
    print(ans)