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

Solution code:
def prime_factorize(N): #素因数分解
    exponent = 0
    while N%2 == 0:
        exponent += 1
        N //= 2
    #if exponent: factorization = [[2,exponent]]
    if exponent: factorization = [[1,pow(2,exponent)]]
    else: factorization = []
    i=1
    while i*i <=N:
        i += 2
        if N%i: continue
        exponent = 0
        while N%i == 0:
            exponent += 1
            N //= i
        factorization.append([1,pow(i,exponent)])
        #factorization.append([i,exponent])
    #if N!= 1: factorization.append([N,1])
    if N!= 1: factorization.append([1,N])
    assert N != 0, "zero"
    return factorization

def Garner_NOmod(alst,mlst):
    x = 0; M = 1
    # 互いに素を仮定
    for a,m in zip(alst,mlst):
        c = (a-x)*modinv(M,m)%m
        x += c*M
        M *= m
    return x

def extgcd(x,y):
    if y==0: return 1,0 #g=x
    r0,r1,s0,s1 = x,y,1,0
    while r1 != 0:
        r0,r1, s0,s1 = r1,r0%r1, s1,s0-r0//r1*s1
    #g = r0
    return s0,(r0-s0*x)//y
    
def modinv(a,MOD):
    x,y = extgcd(a,MOD)
    return x%MOD

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n, = map(int, readline().split())
#lr = [list(map(int, readline().split())) for _ in range(q)]

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

lst = prime_factorize(2*n)

res = []
from itertools import product
for a in product(*lst):
    v = 1
    for i in a: v*= i
    w = 2*n//v
    res.append(Garner_NOmod([0,w-1],[v,w]))

res.sort()
"""
for i in res:
    #print(n,i,i*(i+1)//2)
    assert (i*(i+1)//2)%(n)==0
"""

print(res[1])

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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)

def inv_mod(a, mod):
    b, u, v = mod, 1, 0
    while b:
        t = a // b
        a, b = b, a - t * b
        u, v = v, u - t * v
    return u % mod

def main(N):
    N *= 2
    div = calc_div(N)
    for a in div:
        a = int(a)
        b = N // a
        if np.gcd(a, b) != 1:
            continue
        # b | an + 1
        n = (-inv_mod(a, b)) % b
        k = a * n
        if k == 0:
            k += N
        assert k * (k + 1) % N == 0
        yield k

N = int(read())
print(min(main(N)))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline

n=int(readline())*2

def extgcd(a,b):
	if b==0:
		return (a,1,0)
	else:
		g,y,x=extgcd(b,a%b)
		y-=a//b*x
		return (g,x,y)

def sub(p):
	q=n//p
	g,x,y=extgcd(p,q)
	if g==1:
		x=-x
		while x<=0:
			x+=q
			y+=p
		return x*p
	else:
		return 10**18

ans=10**18
d=1
while d*d<=n:
	if n%d==0:
		ans=min(ans,sub(d),sub(n//d))
	d+=1

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def _is_prime(n):
    '''
    Reference:
    M. Forisek and J. Jancina,
    Fast Primality Testing for Integers That Fit into a Machine Word
    '''
 
    if n <= 1:
        return False
    if n == 2 or n == 7 or n == 61:
        return True
    if n % 2 == 0:
        return False
 
    d = n - 1
    while d % 2 == 0:
        d //= 2
 
    for a in (2, 7, 61):
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = y * y % n
            t <<= 1
        if y != n - 1 and t % 2 == 0:
            return False
    return True
 
 
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)
 
 
def _primitive_root(m: int) -> int:
    if m == 2:
        return 1
    if m == 167772161:
        return 3
    if m == 469762049:
        return 3
    if m == 754974721:
        return 11
    if m == 998244353:
        return 3
 
    divs = [2] + [0] * 19
    cnt = 1
    x = (m - 1) // 2
    while x % 2 == 0:
        x //= 2
 
    i = 3
    while i * i <= x:
        if x % i == 0:
            divs[cnt] = i
            cnt += 1
            while x % i == 0:
                x //= i
        i += 2
 
    if x > 1:
        divs[cnt] = x
        cnt += 1
 
    g = 2
    while True:
        for i in range(cnt):
            if pow(g, (m - 1) // divs[i], m) == 1:
                break
        else:
            return g
        g += 1
        
def factorize(n):
    dd = defaultdict(int)
    for i in range(2,int(n**0.5)+1):
        while n%i==0 and n>0:
            dd[i]+=1
            n//=i
    if n>1:
        dd[n]+=1
    return dd
 
def crt(r, m):
    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)
 
N = int(input())
if N==1:
    print(1)
else:
    D = factorize(N)
    D[2] += 1
    key = list(D.keys())
 
    m = [k**D[k] for k in key]
    ans = 2*N
    for i in range(2**len(key)):
        j = 1
        r = []
        while j < 2**len(key):
            if j&i>0:
                r.append(-1)
            else:
                r.append(0)
            j*=2
        y,z = crt(r,m)
        
        if y==0:
            y = z
        if y==1:
            continue
        ans = min(ans,y)
 
    print(ans)

Submission status: Runtime Error

Solution code:
from math import ceil

n = int(input())
import math
import numpy as np
import decimal
import collections
import itertools
import sys
import random
#Union-Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for i in range(self.n)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.par[p] += self.par[q]
        self.par[q] = p
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.par[self.find(x)]

#素数関連
def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True
#Prime-Factorize
def prime_factorize(n):
    res = []
    while n % 2 == 0:
        res.append(2)
        n //= 2
    f = 3
    while f ** 2 <= n:
        if n % f == 0:
            res.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        res.append(n)
    return res
#nCr
mod = 10 ** 9 + 7
class nCr():
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod
#拡張Euclidの互除法
def extgcd(a, b, d = 0):
    g = a
    if b == 0:
        x, y = 1, 0
    else:
        x, y, g = extgcd(b, a % b)
        x, y = y, x - a // b * y
    return x, y, g
#BIT
class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (self.n + 1)
    def add(self, i, x):
        while i <= self.n:
            self.BIT[i] += x
            i += i & -i
    def query(self, i):
        res = 0
        while i > 0:
            res += self.BIT[i]
            i -= i & -i
        return res
#Associative Array
class AssociativeArray():
    def __init__(self, q):
        self.dic = dict()
        self.q = q
    def solve(self):
        for i in range(self.q):
            Query = list(map(int, input().split()))
            if Query[0] == 0:
                x, y, z = Query
                self.dic[y] = z
            else:
                x, y = Query
                if y in self.dic:
                    print(self.dic[y])
                else:
                    print(0)
#Floor Sum
def floor_sum(n, m, a, b):
    res = 0
    if a >= m:
        res += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        res += n * (b // m)
        b %= m
    y_max = (a * n + b) // m
    x_max = y_max * m - b
    if y_max == 0:
        return res
    res += y_max * (n + (-x_max // a))
    res += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return res
#Z-Algorithm
def z_algorithm(s):
    str_len = len(s)
    res = [0] * str_len
    res[str_len - 1] = str_len
    i, j = 1, 0
    while i < str_len:
        while i + j < str_len and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < str_len and j > res[k] + k:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
class Manacher():
    def __init__(self, s):
        self.s = s
    def coustruct(self):
        i, j = 0, 0 
        s_len = len(self.s)
        res = [0] * s_len
        while i < s_len:
            while i - j >= 0 and i + j < s_len and self.s[i - j] == self.s[i + j]:
                j += 1
            res[i] = j
            k = 1
            while i - k >= 0 and k + res[i - k] < j:
                k += 1
            i += k
            j -= k
#mod-sqrt
def mod_sqrt(a, p):
    if a == 0:
        return 0
    if p == 2:
        return 1
    k = (p - 1) // 2
    if pow(a, k, p) != 1:
        return -1
    while True:
        n = random.randint(2, p - 1)
        r = (n ** 2 - a) % p
        if r == 0:
            return n
        if pow(r, k, p) == p - 1:
            break
    k += 1
    w, x, y, z = n, 1, 1, 0
    while k:
        if k % 2:
            y, z = w * y + r * x * z, x * y + w * z
        w, x = w * w + r * x * x, 2 * w * x
        w %= p
        x %= p
        y %= p
        z %= p
        k >>= 1
    return y
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]
ans = float("inf")
div = make_divisors(2 * n)
for i in div[:ceil(len(div) / 2)]:
    x1, y1, g1 = extgcd(i, 2 * n // i)
    if g1 == 1:
        x1 *= -1
        while x1 <= 0:
            x1 += 2 * n // i
            y1 += i
        ans = min(ans, x1 * i)
    x2, y2, g2 = extgcd(2 * n // i, i)
    if g2 == 1:
        x2 *= -1
        while x2 <= 0:
            x2 += i
            y2 += 2 * n // i
        ans = min(ans, x2 * (2 * n // i))
print(ans)

Submission status: Runtime Error

Solution code:
import sympy.ntheory.modular

N = int(input())
N *= 2
K = [[1, N]]
for i in range(2, max(int(N**0.5)+2, 2)):
    if N % i == 0:
        K.append([i, N//i])

ans = float("inf")
for i in range(len(K)):
    a, b = K[i]
    x = sympy.ntheory.modular.crt([a, b], [0, -1])
    if x is None:
        pass
    else:
        ans = min(ans, x[0])

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
for  i in range(1,N):
  X = i*(i+1)/2/N
  Y = i*(i+1)/2//N
  if X == Y:
    ans = i
    break
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from collections import Counter


# 拡張ユークリッド互除法
# gcd(a,b) と ax + by = gcd(a,b) の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def chineseRem(b1, m1, b2, m2):
    # 中国剰余定理
    # x ≡ b1 (mod m1) ∧ x ≡ b2 (mod m2) <=> x ≡ r (mod m)
    # となる(r. m)を返す
    # 解無しのとき(0, -1)
    d, p, q = egcd(m1, m2)
    if (b2 - b1) % d != 0:
        return 0, -1
    m = m1 * (m2 // d)  # m = lcm(m1, m2)
    tmp = (b2-b1) // d * p % (m2 // d)
    r = (b1 + m1 * tmp) % m
    return r, m


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


N = int(input())
p = prime_factorize(2*N)
c = Counter(p)

if N == 1:
    print(２)

if len(c.keys()) == 1:
    print(N-1)
    exit()

d = [k ** v for k, v in c.items()]

m = len(d)

ans = N-1
for i in range(2 ** m):
    a, b = 1, 1
    for j in range(m):
        if (i >> j) & 1:
            a *= d[j]
        else:
            b *= d[j]

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

    ans = min(ans, chineseRem(0, a, b-1, b)[0])
    ans = min(ans, chineseRem(a-1, a, 0, b)[0])

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
def factorization(num):

    return factor
def main():
  n2=int(input())
  n=n2
  if n==1:
    print(1)
    exit()
  num=n
  factor = []
  while num > 1:
    for i in range(num - 1):
      k = i + 2
      if num % k == 0:
        factor.append(k)
        num = int(num / k)
        break
  if len(factor)==1:
    print(n-1)
    exit()
  num=n

  a=np.array(factor)
  print(a)
  ui, counts = np.unique(a, return_counts=True)
  
  for i in range(ui.size):
    cts=counts[i]
    if cts>1:
      div=ui[i]**(cts//2)
      num=num//div
      counts[i]=cts%2
  n=num
  for uii in ui:
    if n % uii ==0:
      if ((n/uii)-1) %uii==0:
        num=num//uii
  min=num-1
  num=n
  for uii in ui:
    if n % uii ==0:
      if ((n/uii)+1) %uii==0:
        num=num//uii
  min2=num
  if min>min2:
    print(min2)
    exit()
  else:
    print(min)
	exit()
  list2 = []
  for i in range(1,len(factor)+1):
    iter = itertools.combinations(factor,i)
    list2.append(list(iter))
  for all in list2:
    for item in all:
      ji=1
      for cs in item:
        ji=ji*cs
      if((ji*(ji-1))//2)%n2==0:
        print(ji-1)
        exit()
      if((ji*(ji+1))//2)%n2==0:
        print(ji)
        exit()
main()

Submission status: Runtime Error

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        self.n = n
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def query(self, l, r):
        """ 区間和の取得 [l, r) """
        return self.sum(r-1) - self.sum(l-1)
    
    def get(self, i):
        """ 一点取得 """
        return self.query(i, i+1)

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

    def bisearch_fore(self, l, r, x):
        """ 区間[l, r]を左から右に向かってx番目の値がある位置 """
        l_sm = self.sum(l-1)
        ok = r + 1
        ng = l - 1
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if self.sum(mid) - l_sm >= x:
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return INF

    def bisearch_back(self, l, r, x):
        """ 区間[l, r]を右から左に向かってx番目の値がある位置 """
        r_sm = self.sum(r)
        ok = l - 1
        ng = r + 1
        while ok+1 < ng:
            mid = (ok+ng) // 2
            if r_sm - self.sum(mid-1) >= x:
                ok = mid
            else:
                ng = mid
        if ok != l - 1:
            return ok
        else:
            return -INF

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n
        self.tree = [True] * n
        self.grpcnt = n

    def find(self, x):
        """ 根の検索(グループ番号の取得) """
        t = []
        while self.par[x] != x:
            t.append(x)
            x = self.par[x]
        for i in t:
            self.par[i] = x
        return self.par[x]

    def union(self, x, y):
        """ 併合 """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        self.grpcnt -= 1
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            return self.grpcnt
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N = INT()
XY = []
XtoY = [0] * (N+1)
YtoI = [0] * (N+1)
for i in range(N):
    x, y = MAP()
    XY.append((x, y))
    XtoY[x] = (y, i)
    YtoI[y] = i

bit = BIT(N+1)
uf = UnionFind(N)
for i in range(1, N+1):
    bit.add(i, 1)
for x in range(1, N+1):
    y, i = XtoY[x]
    cury = y
    while 1:
        nxty = bit.bisearch_fore(cury+1, N, 1)
        if nxty == INF:
            break
        else:
            j = YtoI[nxty]
            if uf.is_same(i, j):
                break
            else:
                uf.union(i, j)
                cury = nxty
    bit.add(y, -1)

for i in range(N):
    ans = uf.get_size(i)
    print(ans)

Submission status: Runtime Error

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

@author: saito
"""

# %% import phase
import math

# %% define phase

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

# %% process phase

s = int(math.sqrt(2*N))
t = s-1
old = (t*t + t)/2
for i in range(N-s):
    j = i+s;
    new = old + j
    if new % N == 0:
        break
    old = new;
    
# %%output phase
print(j)

Submission status: Runtime Error

Solution code:
z=int(input())

def solv_quadratic_equation(a, b, c):
  """ 2次方程式を解く  """
  D = (b**2 - 4*a*c) ** (1/2)
  x_1 = (-b + D) / (2 * a)
  x_2 = (-b - D) / (2 * a)

  return x_1,x_2

ans=0

i=1

# print(10**15)

# a,b=solv_quadratic_equation(1,1,1000000000000000)

# print(a,b)

while True:

  a,b=solv_quadratic_equation(1,1,-2*z*i)

  if a>=b:
    if a.is_integer():
      # print(a)
      # print(b)
      ans=a
      break
  elif a=<b:
    if b.is_integer():
      # print(a)
      # print(b)
      ans=b
      break

  i+=1

print(int(ans))

Submission status: Runtime Error

Solution code:
    N = int(input())
    ans = resolve(N)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


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):
    # prime factorization
    factorization = sympy.factorint(2 * n)
    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: Runtime Error

Solution code:
N=int(input())
for p in range(1, 2 * N - 1):
    sq = int(math.sqrt(2*N * p))
    if 2*N*p % sq == 0 and 2*N*p ==sq *(sq+1):
        print(sq)
        break

Submission status: Runtime Error

Solution code:
N = int(input())
for p in range(1, 2 * N - 1):
    sq = int(math.sqrt(2*N * p))
    if 2*N*p % sq == 0 :
        print(sq)
        break

Submission status: Runtime Error

Solution code:
import sys


def debug(*x):
    print(*x, file=sys.stderr)


def ex():
    for i in range(2, 100):
        for j in range(1, i - 1):
            if (j * (j + 1) // 2) % i == 0:
                # debug("i, j", i, j)
                break
        else:
            debug("i", i)


def blute(N):
    for i in range(1, N):
        if (i * (i + 1) // 2) % N == 0:
            return i
    return N - 1


#!/usr/bin/env python3
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def factor(n):
    """
    >>> factor(100)
    defaultdict(<class 'int'>, {2: 2, 5: 2})
    >>> factor(103)
    defaultdict(<class 'int'>, {103: 1})
    """
    from math import sqrt
    from collections import defaultdict
    ret = defaultdict(int)
    SQRTN = int(sqrt(n)) + 1
    p = 2
    while p < SQRTN and n > 1:
        while n % p == 0:
            ret[p] += 1
            n //= p
        p += 1
    if n > 1:
        ret[n] += 1
    return ret


def solve_0(N):
    """
    not return minimum answer
    """
    f = factor(N)
    if len(f) == 1:
        return N - 1
    xs = [p ** f[p] for p in f]
    maxx = max(xs)
    rest = N // maxx
    debug("N, maxx, rest", N, maxx, rest)
    for p in range(maxx, N, maxx):
        if (p + 1) % rest == 0:
            return p
        if (p - 1) % rest == 0:
            return p - 1


def solve(N):
    f = factor(N)
    if len(f) == 1:
        return N - 1
    xs = [p ** f[p] for p in f]
    maxx = max(xs)
    rest = N // maxx
    debug("N, maxx, rest", N, maxx, rest)
    for p in range(maxx, N, maxx):
        if (p + 1) % rest == 0:
            return p
        if (p - 1) % rest == 0:
            return p - 1


def main():
    N = int(input())
    print(solve(N))


# tests
T1 = """
11
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
10
"""


def test2():
    """
    >>> test2()
    ok
    """
    for i in range(2, 100):
        debug("blute(i), solve(i)", blute(i), solve(i))
        assert blute(i) == solve(i)
    print("ok")


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Runtime Error

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 = N
i = 0
li = []

while True:
    x_1,x_2 = solv_quadratic_equation(float(1),float(1),float(-2*N))
    if x_1.is_integer() and x_1 > 0:
      li.append(int(x_1))
    if x_2.is_integer() and x_2 > 0:
      li.append(int(x_2))
    N += a
    i += 1
    if i == 100000:
        break
print(min(li))

Submission status: Runtime Error

Solution code:
n=int(input())
for i in range(1,n):
	#print(i)
	if (1+8*n*i)**0.5==int((1+8*n*i)**0.5):
		k=(1+8*n*i)**0.5
		break
print(int((-1+k)/2))

Submission status: Runtime Error

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

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

Solution code:
n=int(input())
for i in range(1,(n-1)//2+1):
	#print(i)
	if (1+8*n*i)**0.5==int((1+8*n*i)**0.5):
		k=(1+8*n*i)**0.5
		break
print(int((-1+k)/2))

Submission status: Runtime Error

Solution code:
from math import sqrt
from math import ceil
def mpfli(N): #minimum prime factor listのこと
    li = [i for i in range(N+1)]
    li2 = [i for i in range(N+1)]
    for i in range(2,ceil(sqrt(N+1))):
        for j in range(2*i, N + 1):
            if li[j]== li2[j]:
                if li[j] % li[i] == 0:
                    li[j] = li[i]
    return li


def pfac(n): #mpf = mpfli(N)
    S = [0] * (n+1)
    while n != 1:
        m = mpf[n]
        S[m] += 1
        n = n // m
    return S


def divofsum(k):
    pk = pfac(k)
    pk2 = pfac(k+1)
    pk.append(0)
    pp = [pk[i] + pk2[i] for i in range(k+2)]
    pp[2] -= 1
    return pp


def check(k):
    flag = True
    dk = divofsum(k) + [0] * (N-k-1)
    for i in range(N + 1):
        if dk[i] < pliN[i]:
            flag = False
            break
    return flag
            

N = int(input())
mpf = mpfli(N)
pliN = pfac(N)
mainflag = False
k = 1
while mainflag == False:
    k += 1
    mainflag = check(k)
print(k)

Submission status: Runtime Error

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
while out%n!=0:
    x,_=cal(base)
    if x!=-1:
        out=cal2(int(x))
    base+=n
print(int(x))

Submission status: Runtime Error

Solution code:
def main2():
    import numpy as np
    N = int(input())
    Ds = np.where((np.arange(1,N+1).cumsum()%N) == 0)
    print(Ds[0][0]+1)
    
main2()

Submission status: Runtime Error

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=out2=1
while out%n!=0 and out2%n!=0:
    x1,x2=cal(base)
    if x1!=-1:
        out=cal2(int(x1))
    base+=n
print(int(x1))

Submission status: Runtime Error

Solution code:
def main2():
    import numpy as np
    N = int(input())
    D = np.arange(1, N+1)
    Ds = np.where((D.cumsum()%N) == 0)
    print(Ds[0][0]+1)
    
main2()

Submission status: Runtime Error

Solution code:
import math

N = int(input())

for a in range(1, N):
    k = math.sqrt(2 * N * a + 1 / 4) - 1 / 2
    if k % 1 == 0:
        break
print(int(k))

Submission status: Runtime Error

Solution code:
import numpy

N = int(input())

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

    i += 1

Submission status: Runtime Error

Solution code:
import sys
def make_prime_table(n):#nまでの整数について，それに含まれる最大の素数
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve

def prime_factorize(n):#1を除く(素因数,指数)のリスト
    result = []
    while n != 1:
        p = prime_table[n]
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        result.append((p, e))
    return result

N=int(input())
prime_table = make_prime_table(N)

if N==1:
    print(1)
    sys.exit()
f=prime_factorize(N)
p,e=f[-1]#最大素べき
#print(p,e)
P=p**e
for a in range(1,10**15//P):
    k=a*P
    if (k*(k-1)//2)%N==0:
        print(k-1)
        sys.exit()
    if (k*(k+1)//2)%N==0:
        print(k)
        sys.exit()