B - Sum is Multiple Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

整数 N が与えられます． 正の整数 k であって，(1+2+\cdots+k) が N の倍数になるもののうち， 最小のものを求めてください． なお，このような正の整数 k が必ず存在することは証明できます．

制約

  • 1 \leq N \leq 10^{15}
  • 入力は全て整数である．

入力

入力は以下の形式で標準入力から与えられる．

N

出力

答えを一行に出力せよ．

入力例 1

11

出力例 1

10

1+2+\cdots+10=55 であり，これは確かに N=11 の倍数です． k \leq 9 で条件を満たすものは存在しないため，k=10 が答えになります．

入力例 2

20200920

出力例 2

1100144

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