C - Minimize Abs 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

正整数 D が与えられます。

非負整数 x,y に対する |x^2+y^2-D| の最小値を求めてください。

制約

  • 1\leq D \leq 2\times 10^{12}
  • 入力は全て整数

入力

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

D

出力

答えを出力せよ。

入力例 1

21

出力例 1

1

x=4,y=2 のとき |x^2+y^2-D| = |16+4-21|=1 となります。

|x^2+y^2-D|=0 を満たすような非負整数 x,y は存在しないので、答えは 1 です。

入力例 2

998244353

出力例 2

0

入力例 3

264428617

出力例 3

32

Score : 300 points

Problem Statement

You are given a positive integer D.

Find the minimum value of |x^2+y^2-D| for non-negative integers x and y.

Constraints

  • 1\leq D \leq 2\times 10^{12}
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

D

Output

Print the answer.

Sample Input 1

21

Sample Output 1

1

For x=4 and y=2, we have |x^2+y^2-D| = |16+4-21|=1.

There are no non-negative integers x and y such that |x^2+y^2-D|=0, so the answer is 1.

Sample Input 2

998244353

Sample Output 2

0

Sample Input 3

264428617

Sample Output 3

32