Problem:


Score : 600 points

Problem Statement

Given is an integer N.
Find the minimum possible positive integer k such that (1+2+\cdots+k) is a multiple of N.
It can be proved that such a positive integer k always exists.

Constraints

1 \leq N \leq 10^{15}

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer in a line.

Sample Input 1

11

Sample Output 1

10

1+2+\cdots+10=55 holds and 55 is indeed a multple of N=11.
There are no positive integers k \leq 9 that satisfy the condition, so the answer is k = 10.

Sample Input 2

20200920

Sample Output 2

1100144



Sample input:
11


Sample output:
10

Submission status: Wrong Answer

Solution code:

import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

def modinv(a, n):
    (x, lastx) = (0, 1); (y, lasty) = (1, 0); p = n
    while p != 0:
       q = a // p; (a, p) = (p, a % p)
       (x, lastx) = (lastx - q * x, x); (y, lasty) = (lasty - q * y, y)
    return lastx % n

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

N = n1()

fact = factorization(N)

if fact[0][0] == 2:
    fact[0][1] += 1
else:
    fact = [[2, 1]] + fact

#print(fact)

ans = 10**16
for n in range(2**len(fact)-1):
    cand = bin(n)[2:].zfill(len(fact))
    k = 1
    q = 1

    for i in range(len(cand)):
        p, t = fact[i][0], fact[i][1]
        if cand[i] == "1":
            k *= p**t
        else:
            q *= p**t

    x = - modinv(k, q) % q
    tmp = k*x

    """
    if k % 2 == 0:
        if x % 2 != 0:
            x *= 2
    else:
        if x % 2 != 0:
            x *= 2
    """

    ans = min(tmp, ans)
    #print(ans, k, x, q, k*x)

ans = min(tmp, ans)

print(ans)

Submission status: Wrong Answer

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(float(1) , float(1) , float(-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: Wrong Answer

Solution code:
n=int(input())


for i in range(int(n**.5)+1,1,-1):
    if n % i ==0:
        for i in range ( 1 , n + 1 ):
            if (((i * (i + 1))) % (2 * n)) == 0:
                print ( i )
                exit(0)
else:print(n-1)

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
''' Created on 2020/09/20 @author: harurun ''' 
import math 
import sys 
pin=sys.stdin.readline 
N=int(pin()) 
j=1 
while 1: 
  i=N*j 
  s=math.sqrt(1+8*i ) 
  if int(s)==s:
    print(int((s-1)//2)) 
    break 
  j+=1

Submission status: Wrong Answer

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 ** 5, dtype=np.int8)
    primes_array[0] = 0
    primes_array[1] = 0
    for p in range(10 ** 5):
        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, m):
        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: Wrong Answer

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: Wrong Answer

Solution code:
import numpy as np
import math
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

N = int(input())
if len(factorization(N)) == 1:
    max_prime = 2
else:
    max_prime = factorization(N)[-1][0]
k = max_prime

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

Submission status: Wrong Answer

Solution code:
''' Created on 2020/09/20 @author: harurun ''' 
import math 
import sys 
pin=sys.stdin.readline 
N=int(pin()) 
j=1 
while 1: 
  i=N*j 
  t=1+8*i 
  s=math.sqrt(t) 
  if int(s)**2==s**2:
    print(int((s-1)//2)) 
    break 
  j+=1

Submission status: Wrong Answer

Solution code:
n = int(input())
s=0

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

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
i = 1
while True:
	x = math.sqrt(1 + 8*n*i)
	i += 1
	if int(x) == x and int(x)%2 == 1:
		print(int((-1 + x)/2))
		break

Submission status: Wrong Answer

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 = pow(t,0.5)
    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: Wrong Answer

Solution code:
N = int(input())

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

m = 1

while K(m).is_integer() == False or K(m) % 2 == 0:    
    m += 1

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

Submission status: Wrong Answer

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 = t**(0.5)
    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: Wrong Answer

Solution code:
import math
n = int(input())
i = 1
while True:
	x = math.sqrt(1 + 8*n*i)
	i += 1
	if int(x) == x and x%2 == 1:
		print(int((-1 + x)/2))
		break

Submission status: Wrong Answer

Solution code:

import math
n = int(input())
for i in range(1, n + 1):
	x = math.sqrt(1 + 8*n*i)
	if int(x) == x and x%2 == 1:
		print(int((-1 + x)/2))
		break

Submission status: Wrong Answer

Solution code:

n = int(input())
s=0
v=0
for i in range(1,n//2):
    s=s+i
    
    if s%n==0:
       print(i)
       break;

Submission status: Wrong Answer

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

def modinv(a, n):
    (x, lastx) = (0, 1); (y, lasty) = (1, 0); p = n
    while p != 0:
       q = a // p; (a, p) = (p, a % p)
       (x, lastx) = (lastx - q * x, x); (y, lasty) = (lasty - q * y, y)
    return lastx % n

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

N = n1()

fact = factorization(N)
#print(fact)

ans = 10**16
for n in range(2**len(fact)-1):
    cand = bin(n)[2:].zfill(len(fact))
    k = 1
    q = 1

    for i in range(len(cand)):
        p, t = fact[i][0], fact[i][1]
        if cand[i] == "1":
            k *= p**t
        else:
            q *= p**t

    x = - modinv(k, q) % q
    tmp = k*x
    if (tmp*(tmp+1) // 2) % N != 0:
        tmp *= 2

    ans = min(tmp, ans)
    #print(ans, k, x, k*x)

print(ans)

Submission status: Wrong Answer

Solution code:
import math

n = float(input())
i = 1.0;
while 1:
    x = -0.5 + math.sqrt(0.25 + 2 * i * n)
    if x.is_integer():
        print(int(x))
        break
    i +=1

Submission status: Wrong Answer

Solution code:
import math

n = float(input("入力"))
i = 1.0;
while 1:
    x = -0.5 + math.sqrt(0.25 + 2 * i * n)
    if x.is_integer():
        print(int(x))
        break
    i +=1

Submission status: Wrong Answer

Solution code:
def main2():
    import numpy as np
    N = int(input())
    head = 0
    c = 0
    while(True):
        Ds = np.arange(1+(c*1000), ((c+1)*1000)).cumsum() + head
        Dm = np.where((Ds%N)==0)
        if(len(Dm[0]>0)):
            print(Dm[0][0]+1+c*1000)
            return
        c += 1
        head += Ds[-1]
    return
main2()

Submission status: Wrong Answer

Solution code:
def P(n):
    a = []
    while n%2 == 0:
        a.append(2)
        n = n//2
    at = 3
    while at*at <= n:
        while n%at == 0:
            a.append(at)
            n = n//at
        at += 2
    if n > 2:
        a.append(n)
    return a


n = int(input())
PR = P(n)
PR.append(2)
dic = {}
HOL = []
ans = 2*n
for x in PR:
    if x in dic:
        dic[x] += 1
    else:
        dic[x] = 1

for x in dic:
    HOL.append((x,dic[x]))


def bt(at, mul):
    global n
    global HOL
    global ans
    oth = mul * (mul-1) // 2
    if oth % n == 0 and oth != 0:
        ans = min(ans,mul-1)
    tts = mul * (mul+1) // 2
    if at >= len(HOL):
        return
    if mul > ans:
        return
    if tts % n == 0:
        ans = mul
        return
    for x in range(0,HOL[at][1]+1):
        bt(at+1, mul * (HOL[at][0]**x))
bt(0,1)


print(ans)

Submission status: Wrong Answer

Solution code:
import math
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: Wrong Answer

Solution code:
import math

N=int(input())
K=int(math.sqrt(N)+1)

def sumxN(N,K):
  for k in range(K,N**2):
    if k*(k+1)/2%N==0:
      return k
    
print(sumxN(N,K))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

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

N = int(readline())
res = []
for i in range(1, N):
  if i*i > 8*N:
    break
  if (8*N)%i:
    continue
  res.append(i)
  res.append(8*N//i)


def sqrt(x):
    ok = 0
    ng = 10**18
    while (ng-ok) > 1:
        med = (ok+ng)//2
        if med*med <= x:
            ok = med
        else:
            ng = med
    return ok
    

M = 8*N

ans = 2*N
for r in res:
    if r == 1:
        continue
    u = M//r
    if u == 1 or u == 2:
        continue
    if gcd(r, u) > 2:
        continue
    gc, xx, yy = egcd(r, u)
    if gc == 1:
        xx *= 2
        yy *= 2
    xx *= -1
    yy *= -1
    xx %= u
    k = xx*r
    Ml = k*(k+2)
    j = (sqrt(1+Ml)-1)//2
    ans = min(ans, j)
print(ans)

Submission status: Wrong Answer

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

def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

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

N = int(readline())

if N == 1:
    print(1)

res = []
for i in range(1, N):
  if i*i > 8*N:
    break
  if (8*N)%i:
    continue
  res.append(i)
  res.append(8*N//i)


def sqrt(x):
    ok = 0
    ng = 10**18
    while (ng-ok) > 1:
        med = (ok+ng)//2
        if med*med <= x:
            ok = med
        else:
            ng = med
    return ok
    

M = 8*N

ans = 2*N
for r in res:
    if r == 1:
        continue
    u = M//r
    if u == 1 or u == 2:
        continue
    if gcd(r, u) > 2:
        continue
    gc, xx, yy = egcd(r, u)
    if gc == 1:
        xx *= 2
        yy *= 2
    xx *= -1
    yy *= -1
    xx %= u
    k = xx*r
    Ml = k*(k+2)
    j = (sqrt(1+Ml)-1)//2
    ans = min(ans, j)
print(ans)

Submission status: Wrong Answer

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

while True:

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

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

  i+=1

print(int(ans))

Submission status: Wrong Answer

Solution code:
import typing
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 base10toN(num, base):
    converted_string, modstring = "", ""
    currentnum = num
    if not num:
        return '0'
    while currentnum:
        mod = currentnum % base
        currentnum = currentnum // base
        converted_string = chr(48 + mod + 7*(mod > 10)) + converted_string
    return converted_string
n=int(input())*2
ans=n-1
i=2
factors=[]
while i*i<=n:
  if n%i==0:
    n=n//i
    if len(factors)>0 and factors[-1]%i==0:
      factors[-1]=factors[-1]*i
    else:
      factors.append(i)
  else:
    i+=1
if n!=1:
  factors.append(n)
for i in range(2**len(factors)):
  s=base10toN(i,2)
  slist=[]
  for j in s:
    slist.append(j)
  slist.reverse()
  for j in range(len(factors)-len(s)):
    slist.append('0')
  left=1
  right=1
  for j in range(len(factors)):
    if slist[j]=='0':
      left=left*factors[j]
    else:
      right=right*factors[j]
  if left*_inv_gcd(left,right)[1]>1:
    ans=min(ans,left*_inv_gcd(left,right)[1]-1)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
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: Wrong Answer

Solution code:
from functools import lru_cache # お好みで。あると同じ素因数分解をするときに楽できる。

# 参考1: https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98
# 参考2: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
# 参考3: https://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%A9%E3%83%BC%E3%83%89%E3%83%BB%E3%83%AD%E3%83%BC%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3%E6%B3%95


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def is_prime(n):
    "Miller Rabin primality test. 2 <= n <= 2 ** 64 is required"
    if n % 2 == 0:
        return n == 2
    d = n - 1
    r = (d & -d).bit_length() - 1
    d >>= r

    # witnesses をいい感じに決める。
    if n < 2152302898747:
        if n < 9080191:
            if n < 2047:
                witnesses = [2]
            else:
                witnesses = [31, 73]
        else:
            if n < 4759123141:
                witnesses = [2, 7, 61]
            else:
                witnesses = [2, 3, 5, 7, 11]
    else:
        if n < 341550071728321:
            if n < 3474749660383:
                witnesses = [2, 3, 5, 7, 11, 13]
            else:
                witnesses = [2, 3, 5, 7, 11, 13, 17]
        else:
            if n < 3825123056546413051:
                witnesses = [2, 3, 5, 7, 11, 13, 17, 19]
            else:
                witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
    # witnesses の決定終了

    for a in witnesses:
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x *= x
            x %= n
            if x == n - 1:
                break
        else:
            return False
    return True


@lru_cache() # お好みで。
def find_factor(n):
    "Find a non-trivial factor of n by using Pollard's rho algorithm."
    m = int(n ** 0.125) + 1
    c = 1
    while True:
        y = 1
        r = 1
        q = 1
        g = 1
        while g == 1:
            x = y
            for _ in range(r):
                y = (y * y + c) % n
            for k in range(0, r, m):
                ys = y
                for _ in range(m):
                    y = (y * y + c) % n
                    q = q * (x - y) % n
                g = gcd(q, n)
                if g != 1:
                    break
            else:  # 残りの k から r までをやる
                ys = y
                for _ in range(r-k):
                    y = (y * y + c) % n
                    q = q * (x - y) % n
                g = gcd(q, n)
            r *= 2

        if g == n:
            g = 1
            while g == 1:
                ys = (ys * ys + c) % n
                g = gcd(x - ys, n)

        if g == n:
            c += 1  # c を変えて続行。
        else:  # g は n の非自明な素因数。
            return g


prime_numbers_200 = [
    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, 101, 103, 107, 109, 113, 127, 131, 
    137, 139, 149, 151, 157, 163, 167, 173, 179, 
    181, 191, 193, 197, 199
]

def fac(n, try_small_factor = True):
    """
    引数 n の素因数分解をして、素因数を昇順に格納したリストを返す。
    ex. fac_small(60) == [2, 2, 3, 5]
    計算量は O(n ^ 1/4) 程度。
    """
    if n == 1:
        return []
    if is_prime(n):
        return [n]

    ret = []
    if try_small_factor:
        for p in prime_numbers_200:
            while n % p == 0:
                ret.append(p)
                n //= p
            if n == 1:
                return ret

    while n != 1 and not is_prime(n):
        f = find_factor(n)
        if is_prime(f):
            while n % f == 0:
                ret.append(f)
                n //= f
        elif is_prime(n // f):
            ret.append(n // f)
            n = f
        else:
            return sorted(ret + fac(f, False) + fac(n // f, False))

    if n == 1:
        return sorted(ret)
    else:
        ret.append(n)
        return sorted(ret)


N = int(input())
N *= 2
factors = fac(N)
rps = []
index = 0
while index < len(factors):
    f = factors[index]
    tmp = f
    index += 1
    while index < len(factors) and factors[index] == f:
        tmp *= f
        index += 1
    rps.append(tmp)

k = 10 ** 18

b = len(rps)
for i in range(1 << b):
    x = 1
    for j in range(b):
        if i & (1 << j):
            x *= rps[j]
    y = N // x
    m = pow(x, -1, y)

    n = (m * x + 1) // y
    if m == 0 or n == 0:
        m += y
        n += x
    k = min(m * x, k)
    if k * (k - 1) % N == 0:
        k -= 1
    # print(x, y, m * x)
    
print(k)

Submission status: Wrong Answer

Solution code:
z=int(input())


sum=0

if z==0:
  print(z)

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


flg=False

ans=0

i=1

while True:

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

  if a>b:
    if a.is_integer():
      flg=True
      ans=a
      break
  elif a<b:
    if b.is_integer():
      flg=True
      ans=b
      break

  i+=1

print(int(ans))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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 = sqrt(t)
    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: Wrong Answer

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(n / 100 * 5) ,10 ** 15):
    s = 1 / 2 * k * (a + k)
    # print(s%n)
    if s % n == 0:
        print(k)
        sys.exit()

Submission status: Wrong Answer

Solution code:
from functools import reduce
from operator import mul

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_ = reduce(mul,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: Wrong Answer

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

def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

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

N = int(readline())

if N == 1:
    print(1)

res = []
for i in range(1, N):
  if i*i > 8*N:
    break
  if (8*N)%i:
    continue
  res.append(i)
  res.append(8*N//i)


def sqrt(x):
    ok = 0
    ng = 10**18
    while (ng-ok) > 1:
        med = (ok+ng)//2
        if med*med <= x:
            ok = med
        else:
            ng = med
    return ok
    

M = 8*N

ans = 2*N
for r in res:
    if r == 1:
        continue
    u = M//r
    if u == 1 or u == 2:
        continue
    if gcd(r, u) > 2:
        continue
    gc, xx, yy = egcd(r, u)
    if gc == 1:
        xx *= 2
        yy *= 2
    xx *= -1
    yy *= -1
    xx %= u
    k = xx*r
    Ml = k*(k+2)
    j = (sqrt(1+Ml)-1)//2
    ans = min(ans, j)
print(ans)

Submission status: Wrong Answer

Solution code:
import math


if __name__ == "__main__":

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

    for k in range(math.floor((2*N) ** 0.5),N-1):
#    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))
            #print("ii : {0}".format(ii))
            break

    print(ans)

Submission status: Wrong Answer

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

n = k()
if n== 1:
  print(1)
  sys.exit()

if n % 2 != 0:
  print(n-1)
else:
  for i in range(0,n,2):
    if i==0:
      continue
    if (i*(i+1)//2) % n == 0:
      print(i)
      break

"""
n = k()
zahyo = []
count = [1]*n

for i in range(n):
  x,y = I()
  for j in range(len(zahyo)):
    if (x>zahyo[j][0] and y>zahyo[j][1]) or (x<zahyo[j][0] and y<zahyo[j][1]):
      count[i] += 1
      count[j] += 1
      count[i] = max(count[i],count[j])
      count[j] = max(count[i],count[j])
  zahyo.append([x,y])
  count

for i in count:
  print(i)
"""

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
import math
p = round(math.sqrt(n))

N = n
for i in range(1,p+2):
  if N%i == 0:
    N = N/i
    s = i

I = 1
while(True):
  S = s * I
  I += 1
  if S*(S-1)/2%n==0 and I != 1:
    print(S-1)
    break
  if S*(S+1)/2%n==0:
    print(S)
    break

Submission status: Wrong Answer

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

n = k()
if n % 2 != 0:
  print(n-1)
else:
  for i in range(1,n):
    if (i*(i+1)//2) % n == 0:
      print(i)
      break

"""
n = k()
zahyo = []
count = [1]*n

for i in range(n):
  x,y = I()
  for j in range(len(zahyo)):
    if (x>zahyo[j][0] and y>zahyo[j][1]) or (x<zahyo[j][0] and y<zahyo[j][1]):
      count[i] += 1
      count[j] += 1
      count[i] = max(count[i],count[j])
      count[j] = max(count[i],count[j])
  zahyo.append([x,y])
  count

for i in count:
  print(i)
"""

Submission status: Wrong Answer

Solution code:
n=int(input())
k=n
d=dict()
for num in range(2,n+1):
    if num*num>n:
        break
    cnt=0
    while k%num==0:
        k//=num
        cnt+=1
    if cnt>0:
        d[num]=cnt
if k>0:
    d[k]=1
maxi=0
for num in d:
    maxi=max(maxi,num)
maxi=maxi*d[maxi]
for i in range(1,n+1):
    if i*i>n:
        break
    if (i*maxi-1)*(i*maxi)%(2*n)==0:
        print(i*maxi-1)
        exit()
    if 2*(i*maxi)*(i*maxi+1)%(2*n)==0:
        print(i*maxi)
        exit()