問題一覧 > 教育的問題

No.2191 Quadratic Expression in One Variable mod Odd Prime

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 24
作問者 : 👑 p-adic / テスター : MasKoaTS
お気に入りにしたユーザー ProblemId : 8684 / 自分の提出
問題文最終更新日: 2022-11-28 21:47:29
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 373 (順位表) の他の問題:

Problem Statement

You are given an odd prime $P$ as input.

　

Let $K$ be the positive integer $\dfrac{P - 1}{2}$. Determine whether the congruence

$\displaystyle n^2 + 3n + K^2 + 4K + 2 \equiv 0 \pmod{P} $

has an integer solution $n$.

Input

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

Constraints

The input satisfies the following constraints:

  • $P$ is an odd prime less than $10^9$

Output

Let $K$ be the positive integer $\dfrac{P - 1}{2}$. If the congruence

$\displaystyle n^2 + 3n + K^2 + 4K + 2 \equiv 0 \pmod{P} $

has an integer solution $n$, print YES; otherwise, print NO.

End the output with a newline.

Sample

Sample 1
Input
3
Output
NO

Here $P = 3$, so $K = 1$. To check whether a congruence modulo $3$ has an integer solution $n$, it suffices to consider only the cases $n \in \{0,1,2\}$, but

$\displaystyle \begin{array}{rcl} &\displaystyle (0^2 + 3 \times 0 + 1^2 + 4 \times 1 + 2) \bmod 3 &\displaystyle = &\displaystyle 7 \bmod 3 = 1 \neq 0 \\ &\displaystyle (1^2 + 3 \times 1 + 1^2 + 4 \times 1 + 2) \bmod 3 &\displaystyle = &\displaystyle 11 \bmod 3 = 2 \neq 0 \\ &\displaystyle (2^2 + 3 \times 2 + 1^2 + 4 \times 1 + 2) \bmod 3 &\displaystyle = &\displaystyle 17 \bmod 3 = 2 \neq 0 \end{array} $

so no integer solution exists.

Sample 2
Input
5
Output
NO

Here $P = 5$, so $K = 2$. To check whether a congruence modulo $5$ has an integer solution $n$, it suffices to consider only the cases $n \in \{0,1,2,3,4\}$, but

$\displaystyle \begin{array}{rcl} &\displaystyle (0^2 + 3 \times 0 + 2^2 + 4 \times 2 + 2) \bmod 5 &\displaystyle = &\displaystyle 14 \bmod 5 = 4 \neq 0 \\ &\displaystyle (1^2 + 3 \times 1 + 2^2 + 4 \times 2 + 2) \bmod 5 &\displaystyle = &\displaystyle 18 \bmod 5 = 3 \neq 0 \\ &\displaystyle (2^2 + 3 \times 2 + 2^2 + 4 \times 2 + 2) \bmod 5 &\displaystyle = &\displaystyle 24 \bmod 5 = 4 \neq 0 \\ &\displaystyle (3^2 + 3 \times 3 + 2^2 + 4 \times 2 + 2) \bmod 5 &\displaystyle = &\displaystyle 32 \bmod 5 = 2 \neq 0 \\ &\displaystyle (4^2 + 3 \times 4 + 2^2 + 4 \times 2 + 2) \bmod 5 &\displaystyle = &\displaystyle 42 \bmod 5 = 2 \neq 0 \\ \end{array} $

so no integer solution exists.

Sample 3
Input
7
Output
YES

Here $P = 7$, so $K = 3$. Setting $n = 5$ gives

$\displaystyle n^2 + 3n + K^2 + 4K + 2 = 5^2 + 3 \times 5 + 3^2 + 4 \times 3 + 2 = 63 \equiv 0 \pmod{7} $

.

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