問題一覧 > 教育的問題

No.2191 一元二次式 mod 奇素数

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

問題文

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

　

正整数 P−12\dfrac{P - 1}{2} を KK と置いた時、合同式

n2+3n+K2+4K+2≡0(modP)\displaystyle n^2 + 3n + K^2 + 4K + 2 \equiv 0 \pmod{P}

に整数解 nn が存在するか否かを判定してください。

入力

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

制約

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

  • PP は 10910^9 未満の奇素数

出力

正整数 P−12\dfrac{P - 1}{2} を KK と置いた時、合同式

n2+3n+K2+4K+2≡0(modP)\displaystyle n^2 + 3n + K^2 + 4K + 2 \equiv 0 \pmod{P}

に整数解 nn が存在する場合はYESと、存在しない場合はNOと出力してください。

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

サンプル

サンプル1
入力
3
出力
NO

今回は P=3P = 3 なので K=1K = 1 です。33 を法とする合同式の整数解 nn の有無を調べるには n∈{0,1,2}n \in \{0,1,2\} の場合のみ考えれば十分ですが、

(02+3×0+12+4×1+2) mod 3=7 mod 3=1≠0(12+3×1+12+4×1+2) mod 3=11 mod 3=2≠0(22+3×2+12+4×1+2) mod 3=17 mod 3=2≠0\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}

であるため、整数解は存在しません。

サンプル2
入力
5
出力
NO

今回は P=5P = 5 なので K=2K = 2 です。55 を法とする合同式の整数解 nn の有無を調べるには n∈{0,1,2,3,4}n \in \{0,1,2,3,4\} の場合のみ考えれば十分ですが、

(02+3×0+22+4×2+2) mod 5=14 mod 5=4≠0(12+3×1+22+4×2+2) mod 5=18 mod 5=3≠0(22+3×2+22+4×2+2) mod 5=24 mod 5=4≠0(32+3×3+22+4×2+2) mod 5=32 mod 5=2≠0(42+3×4+22+4×2+2) mod 5=42 mod 5=2≠0\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}

であるため、整数解は存在しません。

サンプル3
入力
7
出力
YES

今回は P=7P = 7 なので K=3K = 3 です。n=5n = 5 と置くと

n2+3n+K2+4K+2=52+3×5+32+4×3+2=63≡0(mod7)\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もしくは右上の雲マークをクリックしてアカウントを作成してください。