No.551 夏休みの思い出(2)

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 21
作問者 : kuuso1kuuso1 / テスター : btkbtk

0 ProblemId : 1251 / 出題時の順位表

プロローグ

※writerの想定解はC#で1700ms程度かかっているので,LL系では難しいかもしれません.

夏休みと言えば,筆者が子供の頃は夏休みの宿題には計算ドリルにて大量の計算演習が課されたものです.
これは夏休みの宿題ということで,二次方程式の演習を山のように出題されたある年の夏の日の出来事です.

kuuso少年「さすがに毎日毎日二次方程式ばかり解くのは飽きたわ」
神様「ではこれでどうじゃ?」
天から声が聞こえたかと思ったら,目の前の計算ドリルが突然光り輝きました.
眩しさに目を閉じ,しばらくして恐る恐る目を開けるとそこには特に一見何の変哲も無い元の計算ドリルがあります.

kuuso少年「なんだったんだろう,今の光は.まぁいいや」
ひとりごちて計算ドリルを開くとそこに見慣れない違和感を感じました.

(問)次の二次方程式を解け
$X^2 + 2X + 2 \equiv 0$ (mod $5$)

どうやら神様の気まぐれによってmod 素数の世界に放り込まれてしまったようです.
まだ二次方程式は10000問も残っているのに,どうすればいいのかすっかり絶望してしまったkuuso少年.
神様「これはおまけじゃ,ほっほー」
気づくとkuuso少年の左手にはこの世界の鍵ともいうべき一つの数字が握られていました.

問題文

奇素数$P$とその原始根$R$が与えられます.
$Q$問の二次方程式 $ A_i X^2 + B_i X + C_i \equiv 0 \pmod P $ (for $i = 1 $ to $Q$) を解いてください.

入力

$P$ $R$
$Q$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_Q$ $B_Q$ $C_Q$


入力は全て整数であり,それぞれは以下の制約を満たす.
$3\le P \le 10^9$
$2\le R \le P-1$
$1\le Q \le 10^4$
$1 \le A_i < P$ , $1 \le i \le Q$
$0 \le B_i < P$ , $1 \le i \le Q$
$0 \le C_i < P$ , $1 \le i \le Q$
$P$ は素数
$R$ は $P$を法とする原始根
(注) $x \not\equiv 0$ が 素数 $p$の原始根であるとは,任意の$k$ ($1 \le k \le p-2 $)に対して$ x ^ k \not\equiv 1 \pmod p $ となる性質を持つことである.
言い換えると,$(p-1)$ 乗して初めて $1$ になるということでもあります.

出力

出力は$Q$行からなり,$i$問目の二次方程式 $ A_i X^2 + B_i X + C_i \equiv 0 \pmod P $ の解を $i$行目に一行で出力してください.
解は $0 \le X \le P-1$の範囲で,複数ある場合は半角スペース区切りで昇順に全て出力して下さい.
もし解が存在しない場合は $-1$を出力して下さい.
最後に改行して下さい.

サンプル

サンプル1
入力
5 2
3
1 0 0
1 0 1
1 0 2
出力
0
2 3
-1

$1$問目は $X^2 \equiv 0$
$2$問目は $X^2 + 1 \equiv 0$
$3$問目は $X^2 + 2 \equiv 0$
$\pmod 5$ の世界では,$0^2 \equiv 0$,$1^2 \equiv 1$,$2^2 \equiv 4$,$3^2 \equiv 4$,$4^2 \equiv 1$,なので上のようになります.

サンプル2
入力
5 2
3
1 2 0
1 2 1
1 2 2
出力
0 3
4
1 2

原始根について,例えば $\pmod 5$ の世界では,2は原始根です.
$2^0 \equiv 1$,$2^1 \equiv 2$,$2^2 \equiv 4$,$2^3 \equiv 3$,$2^4 \equiv 1$,ですね.
$1 \equiv 2^0$,$2 \equiv 2^1$,$3 \equiv 2^3$,$4 \equiv 2^2$,ですよ.

提出ページヘ