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

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

from collections import Counter
n = int(input())
prime_list = prime_factorize(n)
if n == 1:
    print(1)
    break

cnt = Counter(prime_list)
cnt_values = list(cnt.values())
value_list = [range(i + 1) for i in cnt_values]
iter_list = list(value_list[0])
iter_list = [[i] for i in iter_list]
for v_list in value_list[1:]:
    tmp = []
    for v in v_list:
        for i in iter_list:
            tmp.append(i + [v])
    iter_list = tmp
    
key_list = list(cnt.keys())
ans = n - 1
mod = 2 * n
for i_list in iter_list:
    tmp = 1
    for key, value in zip(key_list, i_list):
        tmp = tmp * pow(key, value)
    if tmp == 1:
        continue
    if tmp * (tmp - 1) % mod == 0:
        ans = min(ans, tmp - 1)
    if tmp * (tmp + 1) % mod == 0:
        ans = min(ans, tmp)
print(ans)

Submission status: Runtime Error

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

from collections import Counter
n = int(input())
prime_list = prime_factorize(n)

cnt = Counter(prime_list)
cnt_values = list(cnt.values())
value_list = [range(i + 1) for i in cnt_values]
iter_list = list(value_list[0])
iter_list = [[i] for i in iter_list]
for v_list in value_list[1:]:
    tmp = []
    for v in v_list:
        for i in iter_list:
            tmp.append(i + [v])
    iter_list = tmp
    
key_list = list(cnt.keys())
ans = n - 1
mod = 2 * n
for i_list in iter_list:
    tmp = 1
    for key, value in zip(key_list, i_list):
        tmp = tmp * pow(key, value)
    if tmp == 1:
        continue
    if tmp * (tmp - 1) % mod == 0:
        ans = min(ans, tmp - 1)
    if tmp * (tmp + 1) % mod == 0:
        ans = min(ans, tmp)
print(ans)

Submission status: Runtime Error

Solution code:
def factorize(n):
    out=[]
    i = 2
    while 1:
        if n%i==0:
            out.append(i)
            n //= i
        else:
            i += 1
        if n == 1:break
        if i > int(n**.5+3):
            out.append(n)
            break
    
    return out
  
N = int(input())
f = factorize(N)[-1]
for i in range(1,10**7):
  if (f*i)*(f*i+1)%(2*N)==0:
    print(f*i)
    exit()

Submission status: Runtime Error

Solution code:
try:
    N=int(input())
    sum=0
   
    for i in range(1,100000)
        sum=sum+i
        if sum%N==0:
            print(i)
            break
except:
    pass

Submission status: Runtime Error

Solution code:
try:
    N=int(input())
    sum=0
    i=1
    for i in range(1,100000)
        sum=sum+i
        if sum%N==0:
            print(i)
            break
except:
    pass

Submission status: Runtime Error

Solution code:
N = int(input())
A = (-1 + math.sqrt(1 + 8 * N))/2
B = N
while not A.is_integer():
    B = B + N
    A = (-1 + math.sqrt(1 + 8 * B))/2
    
print(int(A))

Submission status: Runtime Error

Solution code:
n = input()
num = 1 + 8*n
root = int(math.sqrt(num))
while((root*root)!=num):
  num+=8*n
  root = int(math.sqrt(num))
print((root-1)/2)

Submission status: Runtime Error

Solution code:
N = int(input())
A = float((-1 + math.sqrt(1 + 8 * N))/2)
B = N
while not A.is_integer():
    B = B + N
    A = float((-1 + math.sqrt(1 + 8 * B))/2)
    
print(int(A))

Submission status: Runtime Error

Solution code:
N = int(input())
A = float((-1 + math.sqrt(1 + 8 * N))/2)
B = N
while not A.is_integer():
    B = B + N
    A = float((-1 + math.sqrt(1 + 8 * B))/2)
    
print(A)

Submission status: Runtime Error

Solution code:
n = int(input())
n *= 2
ans = []
ans2 = []
for i in range(2,32*10**6):
  if n % i == 0:
    ans.append(i)
    n //= i
    cnt = 1
    while n % i == 0:
      n //= i
      cnt += 1
    ans2.append(cnt)
if n != 1:
  ans.append(n)
  ans2.append(1)
#print(ans)
#print(ans2)
l = len(ans)
for i in range(l):
  ans[i] **= ans2[i]
#print(ans)
time = [0 for _ in range(l)]
def nex(time):
  for i in range(l):
    if time[i] == 0:
      time[i] = 1
      return time
    else:
      time[i] = 0
  else:
    return 'over'
can = []
while time != 'over':
  x = 1
  y = 1
  for i in range(l):
    if time[i] == 0:
      x *= ans[i]
    else:
      y *= ans[i]
  #print(x,y)
  X = int(x)
  Y = int(y)
  if x > y:
    rec = []
    while y != 1:
      rec.append(x//y)
      x,y = y,x%y
    #print(rec)
    if rec:
      le = len(rec)
      rec.reverse()
      now = [1,-rec[0]]
      for j in range(1,le):
        #print(now)
        now[0],now[1] = now[1],now[0]-now[1]*rec[j]
      #print(now)
      #print(min(abs(X*now[0]),abs(Y*now[1])))
      can.append(min(abs(X*now[0]),abs(Y*now[1])))
  time = nex(time)
print(min(can))

Submission status: Runtime Error

Solution code:
import numpy as np


def main():
    N = int(input())
    a = 1
    while True:
        if isinstance(np.sqrt(2 * a * N), float):
            k = int(np.sqrt(2 * a * N))
            if k * (k + 1) / 2 == a * N:
                print(k)
                break
        a += 1

    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
    N = int(input())
    a = 1
    while True:
        if isinstance(np.sqrt(2 * a * N), float):
            k = int(np.sqrt(2*a*N))
            if k*(k+1)/2 == a*N:
                print(k)
                return
        a += 1



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def euclid(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
 
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
 
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
 
    return a0, b0

n=int(input())
n*=2
soinsu=[]

num=n
for i in range(2,n):
    if(i*i>n):
        if(num!=1):
            soinsu.append([num,1])
        break
    if(num%i!=0):
        continue
    cnt=0
    while(num%i==0):
        cnt+=1
        num//=i
    soinsu.append([i,cnt])

kazu=len(soinsu)


ans=[]
for i in range(2**(kazu-1)):
    a=1
    for j in range(kazu):
        if((i&1<<j)!=0):
            a*=soinsu[j][0]**soinsu[j][1]
    b=n//a
    c,d=euclid(a,b)
    if(c*d==0):
        c+=b
        d+=a
    ans.append(max(a*c,b*d))

print(min(ans)-1)

Submission status: Runtime Error

Solution code:
N=int(input())
sum=[0]*(N+1)
sum[1]=1
ans=0
for i in range(N+1):
  sum[i]=i+sum[i-1]
  
for j in range(N+1):
  if sum[j]%N==0 and j !=0 :
    ans=j
    break;
    
print(ans)

Submission status: Runtime Error

Solution code:
from math import sqrt


def arr():
    return list(map(int, input().split()))


def isPrime(n):
  if (n <= 1):
        return False
    if (n <= 3):
        return True

    if (n % 2 == 0 or n % 3 == 0):
        return False

    i = 5
    while(i * i <= n):
        if (n % i == 0 or n % (i + 2) == 0):
            return False
        i = i + 6

    return True


def getSplit():
    return map(int, input().split())


def check(val):
    s = sqrt(val)
    if s == int(s):
        return False
    l, r = max(1, int(s-10)), int(s+10)
    for i in range(l, r):
        if i*(i+1) == val:
            return i
    return False


def getAns():
    ans = int(input())
    if isPrime(ans):
        print(ans-1)
        return

    m = 1
    val = 2 * m * ans
    start = check(val)
    while not start:
        m += 1
        val = 2 * m * ans
        start = check(val)
    print(start)


getAns()

Submission status: Runtime Error

Solution code:
N=int(input())
sum=[0]*2*N
sum[1]=1
ans=0
for i in range(2*N):
  sum[i]=i+sum[i-1]
  
for j in range(0,2*N):
  if sum[j]%N==0 and j !=0 :
    ans=j
    break;
    
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
    N = int(input())
    a = 1
    while True:
        k = int(np.sqrt(2 * a * N))
        if k*(k+1) == 2*a*N:
            print(k)
            return
        a += 1



if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

for i in range(1, N):
    if (((-1 + math.sqrt(1 + 8 * N * i)) / 2).is_integer()):
        print(int(a))
        break

Submission status: Runtime Error

Solution code:
n = int(input())
s=0
v=[]
for i in range(1,n):
    s=s+i
    if s%n==0:
        v.append(i)

print(v[0])

Submission status: Runtime Error

Solution code:
n=int(input())
count=0
x=1
sm=1
while sm%n!=0:
  	x+=1
 	sm+=x
print(x)