[ProjectEuler] Problem 457 -- A polynomial modulo the square of a prime

N = 10^7。



如果使用暴力法解 n^2 - 3n - 1 = 0 (mod p^2)，時間複雜度大約是 O(N^3)，

所以暴力法不可行，但我們可以先對 N = 10^2 跑暴力法做 benchmark。



對於任一個質數 p，如果解 n^2 - 3n - 1 = 0 (mod p^2) 的時間是 O(N)，

那麼總共的時間複雜度大約是 O(N^2)，這樣也不行。



所以我們有個感覺就是，解 n^2 - 3n - 1 = 0 (mod p^2) 的時間大約要是 O(logN) 之類的玩意。



接下來的方向就很簡單了，根據暴漲的答對人數，不是暴力法，那還會有什麼？