No.2191 一元二次式 mod 奇素数
タグ : / 解いたユーザー数 23
作問者 : 👑
p-adic
/ テスター :
MasKoaTS
問題文
入力に奇素数 $P$ が与えられます。
正整数 $\dfrac{P - 1}{2}$ を $K$ と置いた時、合同式
$\displaystyle n^2 + 3n + K^2 + 4K + 2 \equiv 0 \pmod{P} $
に整数解 $n$ が存在するか否かを判定してください。
入力
入力は次の形式で標準入力から与えられます：$P$
制約
入力は以下の制約を満たします：
- $P$ は $10^9$ 未満の奇素数
出力
正整数 $\dfrac{P - 1}{2}$ を $K$ と置いた時、合同式
$\displaystyle n^2 + 3n + K^2 + 4K + 2 \equiv 0 \pmod{P} $
に整数解 $n$ が存在する場合はYESと、存在しない場合はNOと出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3
出力
NO
今回は $P = 3$ なので $K = 1$ です。$3$ を法とする合同式の整数解 $n$ の有無を調べるには $n \in \{0,1,2\}$ の場合のみ考えれば十分ですが、
$\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 = 5$ なので $K = 2$ です。$5$ を法とする合同式の整数解 $n$ の有無を調べるには $n \in \{0,1,2,3,4\}$ の場合のみ考えれば十分ですが、
$\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 = 7$ なので $K = 3$ です。$n = 5$ と置くと
$\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もしくは右上の雲マークをクリックしてアカウントを作成してください。