#21004: 解法


xavier13540 (柊 四千)

School : 國立臺灣大學
ID : 21783
IP address : [111.240.168.66]
Last Login :
2020-05-31 13:00:02
e373. 一元二次同餘方程式 -- 經典問題 | From: [111.240.173.89] | Post Date : 2020-03-29 03:38

tl; dr: 當 $\color{black}{p=2}$ 時直接特判。當 $\color{black}{p\geq3}$ 時,我們一樣有 $\color{black}{x = \frac{-b+\sqrt{b^2-4ac}}{2a}}$,其中開平方根的部分可以用 CipollaTonelli–Shanks 演算法,時間複雜度分別為 $\color{black}{O(\log p)}$ 與 $\color{black}{O((\log p)^2)}$。

 
ZeroJudge Forum