問題一覧 > 教育的問題

No.2392 Sum of Two Squares

レベル : / AI推定難易度 : 243 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 209
作問者 : 👑 p-adic / テスター : MZKi
お気に入りにしたユーザー ProblemId : 9090 / 自分の提出
問題文最終更新日: 2023-07-28 21:31:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 399 (順位表) の他の問題:

Problem Statement

A prime number $P$ is given as input.

 

Determine whether there exists a pair of positive integers $(i,j)$ satisfying $P = i^2 + j^2$.

Input

The input is given from standard input in the following format:
$P$

Constraints

The input satisfies the following constraints:

  • $P$ is a prime number at most $10^8$

Output

Print Yes if there exists a pair of positive integers $(i,j)$ satisfying $P = i^2 + j^2$, and No otherwise.

Print a newline at the end.

Sample

Sample 1
Input
3
Output
No

We have $1^2 + 1^2 = 2 < 3$, and for any positive integers $i,j$ satisfying $(i,j) \neq (1,1)$, we have

$\displaystyle i^2 + j^2 \geq 2^2 + 1^2 = 5 > 3 $

.

Sample 2
Input
5
Output
Yes

We have $2^2 + 1^2 = 5$.

Sample 3
Input
7
Output
No

We have $\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} $

and for any positive integers $i,j$ satisfying $(i,j) \neq (1,1), (2,1), (2,2)$, we have

$\displaystyle i^2 + j^2 \geq 3^2 + 1^2 = 10 > 7 $

.

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