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

Solution code:


  
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    pass


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()


try:
    N=int(input())
    i=1
    while(i>0):
        sum=(i*(i+1)/2)
        if sum%N==0:
            print(i)
            break
        i=i+1
except:
    pass

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

i = 1
while True:
    k = int((N*2*i)**0.5)
    for ik in range(k, k+100):
        if k*(k+1) == 2*N*i:
            print(k)
            exit()
        if k*(k+1)>2*N*i:
            break

    i=i+1

Submission status: Time Limit Exceeded

Solution code:
import collections
def cal(c):
    x=1+4*c*2
    if x<=0:
        return -1,-1
    else:
        x=x**0.5
        x1=(-1+x)/2
        x2=(-1-x)/2
        return x1,x2 
def cal2(val):
    return (val**2+val)/2
n=int(input())
base=n
out=1
x=1
while out%n!=0:
    x,_=cal(base)
    if x!=-1:
        out=cal2(int(x))
    base+=n
print(int(x))

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal

N = Decimal(input())

i = 1
while True:
    root = Decimal.sqrt(8 * N * i + 1)
    if root == root.to_integral_value():
        print(int((root - 1) / 2))
        exit()

    i += 1

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2020/09/20

@author: harurun
'''
import sys
import decimal 
import math

pin=sys.stdin.readline

N=int(pin())

j=1
while 1:
  i=N*j
  t=1+8*i
  if t%2==1:
    s=decimal.Decimal(t).sqrt().as_integer_ratio()
    if s[1]==1:
      print(int((int(math.sqrt(t))-1)//2))
      break
  j+=1

Submission status: Time Limit Exceeded

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

flag=0
n=n*2
m=n
su=0
while flag==0:
  p=math.isqrt(m)
  if p*(p+1)==m:
    break
  m=m+n
print(p)

Submission status: Time Limit Exceeded

Solution code:

try:
    N=int(input())
    i=1
    while(i>0):
        sum=(i*(i+1)/2)
        if sum%N==0:
            print(i)
            break
        i=i+1
except:
    pass

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
k = 1

for i in range(N):
    S = k / 2 * (k + 1)
    if S % N != 0:
        k += 1
    else:
        break

print(k)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
num = int(math.sqrt(N))
while True:
    ans = num**2/2 + num/2
    if (ans) % N == 0:
        print(num)
        break
    num += 1

Submission status: Time Limit Exceeded

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

m = 1
k = 1
while True:
  k = math.sqrt(2*m*n+0.25) - 0.5
  m += 1
  if k.is_integer():
    if int(k)*(int(k)+1)/2 % n == 0:
      print(int(k))
      break

Submission status: Time Limit Exceeded

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

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
    for i in range(1, n // tmp + 1):
        if (tmp * i) * ((tmp * i) - 1) % mod == 0:
            ans = min(ans, (tmp * i) - 1)
        if (tmp * i) * ((tmp * i) + 1) % mod == 0:
            ans = min(ans, tmp * i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)

    k = 1
    i = 1
    while True:
        a1 = k * (k+1)
        a2 = 2 * i * N
        d1 = a1 - a2
        if d1 == 0:
            break
        elif d1 > 0:
            i += 1
        else:
            k += 1
    print(k)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

while True :
  a = int(math.sqrt(2*c*n))
  b = a*(a+1)
  if b == 2*c*n :
    break
  c += 1

print(a)

Submission status: Time Limit Exceeded

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

flag=0
m=0
su=0
while flag==0:
  m=m+1
  p=int(math.sqrt(n*2*m))
  if p*(p+1)==n*2*m:
    break
print(p)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
k = 1
s = 1
while(s%n!=0):
  k += 1
  s += k
print(k)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
rem = 0
digit = 0
end = True
while end:
    for n in range(1,N):
        rem = (rem + n) % N
        if rem == 0:
            end = False
            break
    if end:
        digit += 1
print(digit * N + n)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
k = 1

for i in range(N):
    S = k / 2 * (k + 1)
    if S % N != 0:
        k += 1
    else:
        break

print(k)

Submission status: Time Limit Exceeded

Solution code:
def tmp(n):
    return (n+1)*n//2

n = int(input())
res = 1
while tmp(res)%n != 0:
    res+=1
print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
k=1
while True:
    sum_k = k*(k+1)/2
    if sum_k%n == 0:
        print(k)
        exit()
    k += 1

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

flag=0
m=0
su=0
while flag==0:
  m=m+1
  p=int((n*2*m)**0.5)
  if p*(p+1)==n*2*m:
    break
print(p)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":

    N = int(input())
    ans = 1
    ii = 0.00

    for k in range(1,N):
        ii = k * (k+1) / (2*N)
        if True == ii.is_integer() :
            ans = k
            #print("ans = k : {0}".format(ans))
            break

    print(ans)

Submission status: Time Limit Exceeded

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

for i in range(int(math.sqrt(2*N)), 2*N):
  if (i*(i+1)) % (2*N) == 0:
    print(i)
    exit()

Submission status: Time Limit Exceeded

Solution code:
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math


def solve(N):

    k=int((-1+math.sqrt(1+8*N))/2)
    cand=(k/2)*(k+1)
    while cand%N!=0:
        k+=1
        cand+=k
    return k

N=readInt()
print(solve(N))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

ans = 1
while ans*(ans + 1) / 2 % n != 0:
  ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import sys
sum_k = 0
for k in range(1,sys.maxsize):
  sum_k += k
  if(sum_k % N == 0):
    print(k)
    break

Submission status: Time Limit Exceeded

Solution code:
import math
import random


class Prime:
    seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

        :param n:
        :return: boolean
        """
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed+1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes


prime = Prime()

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())
d = prime.find_factors(N * 2)
l = [x ** y for (x, y) in d.items()]
m = len(l)
ans = 2 * N
for bit in range(1 << m):
    x = 1; y = 1
    for i in range(m):
        if bit & (1 << i):
            x *= l[i]
        else:
            y *= l[i]
    lx, ly = gcd_ext(x, y)
    # print(x, lx, y, ly, lx % y * x)
    if lx % y:
        ans = min(ans, lx % y * x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math


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 = math.sqrt(val)
    if s == int(s):
        return False
    i = math.floor(s)
    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: Time Limit Exceeded

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())
x1, x2 = solv_quadratic_equation(1,1,-2*N)
k = int(min(x1,x2))
if k <= 0:
    k = int(max(x1,x2))

while True:
    if ((k/2) + (k**2 / 2)) % N == 0:
        print(k)
        break
    k += 1

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import sys
for k in range(1,sys.maxsize):
  sum_k = (1 + k) * k / 2
  if(sum_k % N == 0):
    print(k)
    break

Submission status: Time Limit Exceeded

Solution code:
def cal(x):
    return x**2+x
n=int(input())
base=int(n**0.5)
out=cal(base)
while out%n!=0:
    base+=1
    out=cal(base)
    out/=2
print(base)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
res = 1
counter = 1
while res % n != 0:
    counter += 1
    res += counter
print(counter)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from decimal import *
import decimal
N=int(input())
getcontext().prec=30
"""
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=Decimal(1+8*a*N).sqrt()
    #print(t)
    #print(t.to_integral_value())
    n=t.to_integral_value()
    if (pow(n,Decimal(2),1+8*a*N)==0)and(int(t)%2==1):
        print((int(t)-1)//2)
        break
    a=a+1

Submission status: Time Limit Exceeded

Solution code:
import collections
def cal(x):
    return x**2+x
base=1
out=1
n=int(input())
while out%n!=0:
    base+=1
    out=cal(base)
    out/=2
print(base)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
sum=0
i=1
while(i<=N):
    sum=sum+i
    if sum%N==0:
        print(i)
        break
    i=i+1

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from math import *
from decimal import *
N=int(input())
getcontext().prec=30
"""
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=Decimal(1+8*a*N).sqrt()
    #print(t)
    #print(t.to_integral_value())
    n=t.to_integral_value()
    if ((n*n)%(1+8*a*N)==0)and(int(t)%2==1):
        print((int(t)-1)//2)
        break
    a=a+1

Submission status: Time Limit Exceeded

Solution code:
l = int(input())
s = 0
i = 0
while True:
  i += 1
  s += i
  if s % l == 0:
    print(i)
    break

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
c = 0
a = 1
b = 2
while c == 0:
  if a%n == 0 and n <= a:
    c = 1
    break;
  a += b
  b += 1
print(b-1)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal

N = int(input())
for a in range(1,10**15):
    n = (-1 + (Decimal(1 + 4 * 1 * 2*a*N))**Decimal(0.5)) / 2
    if n == int(n.as_integer_ratio()[0] / n.as_integer_ratio()[1]):
        print(int(n))
        break

Submission status: Time Limit Exceeded

Solution code:
def sum(k):
    result = 0
    result = (1+k)*int(k/2 + 1/2)
    return result
N = int(input())
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())
sum_k = 0
for i in range(1,n+1):
    sum_k += i
    if sum_k%n == 0:
        break
    else:
        sum_k %= n
print(i)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

from collections import Counter
from itertools import product


min2 = lambda x,y: x if x < y else y

def lcm(A):
    m = 1
    for a in A:
        m *= a//gcd(m,a)
    return m


def chinese_remainder_theorem(R, M):
    """
    returns x and lcm(M) s.t.
    all(x%m == r for r,m in zip(R,M))
    """
    s = 0
    big_m = lcm(M)
    for m,r in zip(M,R):
        p = big_m//m
        s += r * p * pow(p, -1, m)
        s %= big_m
    return s, big_m


# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n



N = int(input())

factors = Counter(prime_factors(N))
if factors[2] > 0:
    factors[2] += 1
mods = [f**p for f,p in factors.items()]

res = N
for R in product(*((0,m-1) for m in mods)):
    t = chinese_remainder_theorem(R, mods)[0]
    if t > 0:
        res = min2(res, t)

print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
i = int(n**0.5)
a = 1
while True:
  r=2*a*n
  p = int(r**0.5)
  while True:
    if p**2>=r:
      break
    if (p+1)**2<=r:
      break
    if p*(p+1)==r:
      print(p)
      quit()
    p-=1
  a+=1

Submission status: Time Limit Exceeded

Solution code:
val = int(input())

i = 1
while(True):
    tmp = i*(1+i) / 2
    if tmp%val == 0:
        print(i)
        break
    i += 1

Submission status: Time Limit Exceeded

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

start = int(math.sqrt(2*n))

for i in range(start,10**15) :
  if (i*(i+1))%(2*n)  == 0 :
    ans=i
    break
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

k = 1
while True:
    if k*(k+1)//2 % N == 0:
        print(k)
        break
    k += 1

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
i=1
x=0
while True:
  x=(x+i)%N
  if x==0:
    print(i)
    break
  i+=1

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
k=1
while True:
    k_sum = int((1/2)*k*(k+1))
    if k_sum % N == 0:
        print(k)
        break
    k += 1

Submission status: Time Limit Exceeded

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)and(int(t)%2==1):
        print((-1+int(t))//2)
        break
    a=a+1

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

b = True
k = 0

while b:
    k += 1
    if (k * (k+1) / 2) % n == 0:
        b = False


print(k)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
k = 1
while True:
  if (1/2*k*(k+1)) % N == 0:
    print(k)
    break
  else:
    k += 1

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

Submission status: Time Limit Exceeded

Solution code:
a=int(input())

import math
b = math.sqrt(a)
c = int(b/1)
while 1:
    d =int (c*(c+1)/2)
    if(d%a == 0):
        print(c)
        exit()
    c+=1

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
m = int((-1+(1+8*N)**0.5)/2)
for i in range(m, N+1):
  if int(i*(i+1)/2) % N == 0:
    print(i)
    break

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2020/09/20

@author: harurun
'''
import math
import sys
pin=sys.stdin.readline 

N=int(pin())

k=int((-1+math.sqrt(1+8*N))//2)
while 1:
  if (k*(k+1)//2)%N==0:
    print(k)
    break
  k+=1

Submission status: Time Limit Exceeded

Solution code:
a=int(input())

import math
#b = math.sqrt(a)
#c = int(b/1)
c=1
while 1:
    d =int (c*(c+1)/2)
    if(d%a == 0):
        print(c)
        exit()
    c+=1

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

ans = 0
i = 1

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
sum=0
ans=0
for i in range(1,N+1):
  sum=sum+i
  if sum%N==0:
    ans=i
    break;
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil as C, floor as F, sqrt, gcd as G
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data) 

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())


n = I()

def sumseq(k):
    return k * (k+1)/2

ans = 1
while sumseq(ans) % n != 0:
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    k = 1
    while True:
        if (k * (k + 1)) % (2 * N) == 0:
            break
        k += 1
    
    print(k)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


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


n = int(input())
ans = 1
while ((ans*(ans+1))//2) % n != 0:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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