e373: 一元二次同餘方程式
Tags : 數學 數論
Accepted rate : 1人/2人 ( 50% ) [非即時]
評分方式:
Strictly

最近更新 : 2020-03-14 17:21

Content

給定質數 $\color{black}{p}$ 與三個非負整數 $\color{black}{a, b, c}$,其中 $\color{black}{0 \leq a, b, c \leq p-1}$ 且 $\color{black}{a \neq 0}$,請找出同餘方程式 $\color{black}{ax^2+bx+c \equiv 0\ (\operatorname{mod}p)}$ 在 $\color{black}{\{0, 1, \ldots, p-1\}}$ 內的根。

Input

本題的輸入檔有多筆測試資料,請讀至檔案尾。
每筆測試資料佔一行,包含以一空白隔開的四個非負整數 $\color{black}{p, a, b, c}$。

  • 測試資料總數不超過 $\color{black}{10^5}$。
  • $\color{black}{p}$ 為質數且 $\color{black}{2 \leq p < 2^{31}}$。
  • $\color{black}{0 \leq a, b, c \leq p-1}$ 且 $\color{black}{a \neq 0}$。
Output

對於每筆測試資料,輸出一行,包含方程式 $\color{black}{ax^2+bx+c \equiv 0\ (\operatorname{mod}p)}$ 在 $\color{black}{\{0, 1, \ldots, p-1\}}$ 內的根。如果有多個根,請以一空白隔開由小到大輸出。如果不存在這樣的 $\color{black}{x}$,請輸出 "no solution" (不含引號)。

Sample Input #1
2 1 1 0
3 2 1 2
5 4 3 2
2147483647 123456789 999999999 987654321
Sample Output #1
0 1
2
no solution
516628045 1897947583
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (100%): 10.0s , <10M
Hint :
Tags:
數學 數論
出處:
經典問題 [管理者:
xavier13540 (柊 四千)
]


ID User Problem Subject Hit Post Date
21004
xavier13540 (柊 四千)
e373
解法
123 2020-03-29 03:38