問題一覧 > 教育的問題

No.2392 二平方和

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 208
作問者 : 👑 p-adic / テスター : MZKi
0 ProblemId : 9090 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-07-28 21:31:47

問題文

入力に素数 PP が与えられます。

 

P=i2+j2P = i^2 + j^2 を満たす正整数の組 (i,j)(i,j) が存在するか否かを判定してください。

入力

入力は次の形式で標準入力から与えられます:
PP

制約

入力は以下の制約を満たします:

  • PP10810^8 以下の素数

出力

P=i2+j2P = i^2 + j^2 を満たす正整数の組 (i,j)(i,j) が存在する場合はYesと、存在しない場合はNoと出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3
出力
No

12+12=2<31^2 + 1^2 = 2 < 3 であり、(i,j)(1,1)(i,j) \neq (1,1) を満たすいかなる正整数 i,ji,j に対しても

i2+j222+12=5>3\displaystyle i^2 + j^2 \geq 2^2 + 1^2 = 5 > 3

となります。

サンプル2
入力
5
出力
Yes

22+12=52^2 + 1^2 = 5 です。

サンプル3
入力
7
出力
No

12+12=2<722+12=5<722+22=8>7\displaystyle \begin{array}{rcl} \displaystyle 1^2 + 1^2 &\displaystyle = &\displaystyle 2 < 7 \\ \displaystyle 2^2 + 1^2 &\displaystyle = &\displaystyle 5 < 7 \\ \displaystyle 2^2 + 2^2 &\displaystyle = &\displaystyle 8 > 7 \end{array}

であり、(i,j)(1,1),(2,1),(2,2)(i,j) \neq (1,1), (2,1), (2,2) を満たすいかなる正整数 i,ji,j に対しても

i2+j232+12=10>7\displaystyle i^2 + j^2 \geq 3^2 + 1^2 = 10 > 7

となります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。