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:
# -*- 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 << 50


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, INF):
        t = K*i
        j = b.bisect_left(t, 1, INF)
        if f(j) == t:
            return j


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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, INF):
        t = K*i
        j = b.bisect_left(t, 1, INF)
        if f(j) == t:
            return j


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Solution code:
N = int(input())
if N==1:
    print(1)
    exit()

f = N if N%2 else 2*N
from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

fac = factorize(f)
step = len(fac)
for k,v in fac.items():
    step = max(step, k**v)

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

print(N*2-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

a=factorization(n)
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 sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# from atcoder.fenwicktree import FenwickTree

# available on Google, not available on Codeforces
# import numpy as np
# import scipy

# from atcoder.math import crt


def prime_factors(nr):
    i = 2
    factors = []
    while i <= nr:
        if i > math.sqrt(nr):
            i = nr
        if (nr % i) == 0:
            factors.append(int(i))
            nr = nr / i
        elif i == 2:
            i = 3
        else:
            i = i + 2
    return factors


def solve(k):  # fix inputs here
    console("----- solving ------")

    # console(prime_factors(k))
    # console(prime_factors(1100144))
    # console(prime_factors(1100144+1))
    # console((1100144+1)*(1100144)%7575345)

    # y = crt([1,0], [8,k//8])
    # console(k,y)

    # let z be a multple of 2k
    # check if 8z+1 is a square
    for z in range(8*k+1, 10**25, 8*k):
        y = z
        if math.isqrt(y)**2 == y:
            res = (math.isqrt(y) - 1) // 2
            # console(prime_factors(y))
            # console(prime_factors(res))
            # console(prime_factors(res+1))
            # console(prime_factors((res+1)*res))
            return res

    return -1




def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
# inp = sys.stdin.readlines()

for case_num in [1]:
    # read line as a string
    # strr = input()

    # read line as an integer
    k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    # lst = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    # grid = []
    # for n in range(nrows):
    #     grid.append(list(map(int,inp[n+1].split())))

    res = solve(k)  # please change
    
    # res = "\n".join(str(x) for x in res)
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import chain, combinations
import numpy as np
import numba


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


@numba.njit
def search_prime(pq, lower=10 ** 6, upper=32 * 10 ** 6):
    for p in range(lower, upper):
        if pq % p == 0:
            q = pq // p
            return p, q
    return 1, pq


def solve(n):
    # sieve
    primes_array = np.ones(10 ** 6, dtype=np.int8)
    primes_array[0] = 0
    primes_array[1] = 0
    for p in range(10 ** 6):
        if primes_array[p] == 1:
            primes_array[p * p::p] = 0
    primes = np.where([primes_array > 0])[1]
    # 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:
        p, q = search_prime(m)
        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 = np.int(np.prod(s))
        q = 2 * n // p
        if p == 1 or q == 1:
            continue
        a, x, y = ext_gcd(p, q)
        if x < 0:
            res = min(res, abs(p * x))
            # print(p, q, abs(p * x), q * y)
    # print(res)
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(11) == 10
    assert solve(20200920) == 1100144


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import chain, combinations
import numpy as np


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


def solve(n):
    # sieve
    primes_array = np.ones(10 ** 6, dtype=np.int8)
    primes_array[0] = 0
    primes_array[1] = 0
    for p in range(10 ** 6):
        if primes_array[p] == 1:
            primes_array[p * p::p] = 0
    primes = np.where([primes_array > 0])[1]
    # print(primes)
    # prime factorization
    factorization = defaultdict(int)
    m = 2 * n
    for p in primes:
        while m % p == 0:
            m = m // p
            factorization[p] += 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
            m = 1
            break
    if m > 1:
        factorization[m] += 1
    # print(factorization)
    factor_list = []
    for k in factorization.keys():
        factor_list.append(k ** factorization[k])

    # trivial answer
    if n % 2 == 1:
        res = n - 1
    else:
        res = 2 * n - 1

    # power set
    for s in chain.from_iterable(combinations(factor_list, r) for r in range(len(factor_list) + 1)):
        p = np.int(np.prod(s))
        q = 2 * n // p
        if p == 1 or q == 1:
            continue
        a, x, y = ext_gcd(p, q)
        if x < 0:
            res = min(res, abs(p * x))
            # print(p, q, abs(p * x), q * y)
    # print(res)
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(11) == 10
    assert solve(20200920) == 1100144


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
 
flag=0
n=n*2
m=n
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:
n=int(input())
ans=0
temp=1
dif=2
c=1
while(1):
    if(temp%n==0):
        ans=c
        break
    temp=temp+dif
    dif=dif+1
    c=c+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby

N = int(input())
def fast_prime_factorization(n):
    # 素因数分解（ロー法）  O(n^(1/4) polylog(n))
    from subprocess import Popen, PIPE
    return list(map(int, Popen(["factor", str(n)], stdout=PIPE).communicate()[0].split()[1:]))

def a(n):
    if n == 1:
        return 1
    f = fast_prime_factorization(n if n%2 else 2*n)
    step = max(v ** len(list(gr)) for v, gr in groupby(f))
    for m in range(step, 2*n, step):
        if m * (m-1) // 2 % n == 0:
            return m-1
        if m * (m+1) // 2 % n == 0:
            return m

print(a(N))

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
def prime_factors(N): #素因数 1を含まないことに注意
    ret = []
    middle = int( N**(1/2))
    tmp = N
    for i in range(2, middle+1):
        if tmp%i == 0:
            t = 1
            while tmp%i == 0:
                tmp //= i
                t *= i
            ret.append(t)
    if tmp != 1:
        ret.append(tmp)
    return ret

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

def main():
    N = int( input())
    P = prime_factors(2*N)
    M = len(P)
    ans = 2*N-1
    for p in product( range(2), repeat=M):
        x = 1
        for i, t in enumerate(p):
            if t == 1:
                x *= P[i]
        y = N*2//x
        if x == 1:
            if y-1 < ans:
                ans = y-1
            continue
        if y == 1:
            if x-1 < ans:
                ans = x-1
            continue
        _, a, b = xgcd(x,y)
        now = -a*x
        # print(x, y, a, b)
        if a < 0:
            pass
        else:
            now = -b*y
        if now < ans:
            ans = now
    print(ans)
        
        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#ALC1 B
import math
N = int(input())

def sumis(k):
    return int(((1 + k) * k) / 2)

i = 1
loopLimit = 100
while(True):
    test = N * i
    hikaku = int(math.sqrt(test * 2))
    for j in range(loopLimit):
        hikaku2 = sumis(hikaku + j)
        if (hikaku2 == test):
            print(hikaku + j)
            exit()
        if (hikaku2 > test):
            break
    i += 1

Submission status: Time Limit Exceeded

Solution code:
#ALC1 B
import math
N = int(input())

def sumis(k):
    return int(((1 + k) * k) / 2)

i = 1
loopLimit = 100
while(True):
    test = N * i
    hikaku = int(math.sqrt(test))
    for j in range(loopLimit):
        hikaku2 = sumis(hikaku + j)
        if (hikaku2 == test):
            print(hikaku + j)
            exit()
        if (hikaku2 > test):
            break
    i += 1

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
for i in range(1,10**7+1):
    Ni = N*i
    n = math.floor(math.sqrt(2*Ni))
    if (n*(n+1))%N == 0:
        ans = n
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numba import njit
@njit
def resolve(N):
    i = 2
    while True:
        ii = int(i ** 2)
        check = (ii - 1) % (8 * N)
        if check == 0 and i % 2 == 1:
            break
        i += 1
    ans = (i - 1) // 2
    return ans

def main():
    N = int(input())
    ans = resolve(N)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ttl = 0
i  = 1

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 17:00:46 2020

@author: saito
"""

# %% import phase

# %% define phase

# %% input phase
N = int(input())

# %% process phase
old = 0
for i in range(N):
    j = i+1;
    new = old + j
    if new % N == 0:
        break
    old = new;
    
# %%output phase
print(j)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    i = 2
    while True:
        ii = int(i ** 2)
        check = (ii - 1) % (8 * N)
        if check == 0 and i % 2 == 1:
            break
        i += 1
    ans = (i - 1) // 2
    i - 1


    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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
while True:
    t += delta
    sq = int(sqrt(t))
    if sq*sq != t:
        continue
    a = (-1+sq)/2
    b = (-1-sq)/2
    ans = float('inf')
    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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

import math 
_1_50 = 1 << 50  # 2**50 == 1,125,899,906,842,624

def isqrt(x):
    """Return the integer part of the square root of x, even for very
    large integer values."""
    if x < 0:
        raise ValueError('square root not defined for negative numbers')
    if x < _1_50:
        return int(math.sqrt(x))  # use math's sqrt() for small parameters
    n = int(x)
    if n <= 1:
        return n  # handle sqrt(0)==0, sqrt(1)==1
    # Make a high initial estimate of the result (a little lower is slower!!!)
    r = 1 << ((n.bit_length() + 1) >> 1)
    while True:
        newr = (r + n // r) >> 1  # next estimate by Newton-Raphson
        if newr >= r:
            return r
        r = newr

n = inp()
delta = 8*n
t = 1
from math import sqrt
while True:
    t += delta
    sq = isqrt(t)
    if sq*sq != t:
        continue
    a = (-1+sq)/2
    b = (-1-sq)/2
    ans = float('inf')
    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: Time Limit Exceeded

Solution code:
import math

n = int(input())

b = True
c = 0

while b:
    c += 1
    k = int(math.sqrt(2 * c * n))
    if (k * (k+1) )  == 2 * c * n:
        b = False



print(k)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

Sum = 1
k = 2
while (Sum / N).is_integer() == False:
    Sum += k
    k += 1

print(k - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# from atcoder.fenwicktree import FenwickTree

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def prime_factors(nr):
    i = 2
    factors = []
    while i <= nr:
        if i > math.sqrt(nr):
            i = nr
        if (nr % i) == 0:
            factors.append(int(i))
            nr = nr / i
        elif i == 2:
            i = 3
        else:
            i = i + 2
    return factors


def solve(k):  # fix inputs here
    console("----- solving ------")

    # let z be a multple of 2k
    # check if 8z+1 is a square
    for z in range(k, 10**25, k):
        y = 8*z + 1
        # z = (k//2 - 1) * z
        # console(z)
        if math.isqrt(y)**2 == y:
            return (math.isqrt(y) - 1) // 2

    return -1




def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
# inp = sys.stdin.readlines()

for case_num in [1]:
    # read line as a string
    # strr = input()

    # read line as an integer
    k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    # lst = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    # grid = []
    # for n in range(nrows):
    #     grid.append(list(map(int,inp[n+1].split())))

    res = solve(k)  # please change
    
    # res = "\n".join(str(x) for x in res)
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7
n = I()

# 等差数列の和を使う

a = 1

for k in range(int(max(1, n / 100 * 5)) ,10 ** 15):
    s = 1 / 2 * k * (a + k)
    # print(s%n)
    if s % n == 0:
        print(k)
        sys.exit()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input()) 
flag=0
n=n*2
m=n
p=1
while flag==0:
  while p*p<m:
    p=p+1
  p=p-1
  if p*(p+1)==m:
    break
  m=m+n
print(p)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

while True:
  a += 1
  sq = math.sqrt(2*a*n)
  k = math.floor(sq)
  if k*(k+1)==2*a*n:
    break
print(k)

Submission status: Time Limit Exceeded

Solution code:
# cook your dish here

n = int(input());
l = 1
r = 1000000000000000000
ans = -1

while(l<=r):
    mid = l + (r-l)//2;
    val = (mid * (mid + 1))/2;
    if(val >= n):
        r = mid-1;
        ans = mid;
    else:
        l = mid +1;
        
while(( (ans*(ans+1))//2 )%n != 0):
    ans+=1
        
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7
n = I()

# 等差数列の和を使う

a = 1

for k in range(1,10 ** 15):
    s = 1 / 2 * k * (a + k)
    # print(s%n)
    if s % n == 0:
        print(k)
        sys.exit()

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
    sum=0
    while(i>0):
        sum=sum+i
        if sum%N==0:
            print(i)
            break
        i=i+1
except:
    pass

Submission status: Time Limit Exceeded

Solution code:
from math import prod

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())
if N == 1:
  print(1)
  exit()
elif N == 2:
  print(3)
  exit()
f = factorize(N)
if set(f)=={2}:
  f_ = prod(f)
else:
  f_ = f[-1]
for i in range(1,10**7):
  if (f_*i-1)*(f_*i)%(2*N)==0:
    print(f_*i-1)
    exit()
  elif (f_*i)*(f_*i+1)%(2*N)==0:
    print(f_*i)
    exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7
import math
n = I()

# 等差数列の和を使う

a = 1

for k in range(1,10 ** 15):
    s = 1 / 2 * k * (a + k)
    # print(s%n)
    if s % n == 0:
        print(k)
        sys.exit()

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 ik*(ik+1) == 2*N*i:
            print(ik)
            exit()
        if ik*(ik+1)>2*N*i:
            break
    i=i+1