問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 47
作問者 : kuuso1 / テスター : btk
0 ProblemId : 1251 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-07-27 23:53:31

プロローグ

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

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

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

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

(問)次の二次方程式を解け
X2+2X+20 (mod 5)

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

問題文

奇素数Pとその原始根Rが与えられます.
Q問の二次方程式 AiX2+BiX+Ci0(modP) (for i=1 to Q) を解いてください.

入力

P R
Q
A1 B1 C1
A2 B2 C2

AQ BQ CQ


入力は全て整数であり,それぞれは以下の制約を満たす.
3P109
2RP1
1Q104
1Ai<P , 1iQ
0Bi<P , 1iQ
0Ci<P , 1iQ
P は素数
RPを法とする原始根
(注) x0 が 素数 pの原始根であるとは,任意のk1kp2)に対してxk1(modp) となる性質を持つことである.
言い換えると,(p1) 乗して初めて 1 になるということでもあります.

出力

出力はQ行からなり,i問目の二次方程式 AiX2+BiX+Ci0(modP) の解を i行目に一行で出力してください.
解は 0XP1の範囲で,複数ある場合は半角スペース区切りで昇順に全て出力して下さい.
もし解が存在しない場合は 1を出力して下さい.
最後に改行して下さい.

サンプル

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

1問目は X20
2問目は X2+10
3問目は X2+20
(mod5) の世界では,020121224324421,なので上のようになります.

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

原始根について,例えば (mod5) の世界では,2は原始根です.
201212224233241,ですね.
120221323422,ですよ.

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