BZOJ5104 Fib数列

题意

在 $mod\ \ 10^9+\color{red}9$ 的意义下求出数字 $n$ 在 Fib 数列中出现在哪个位置
由于没有 spj如果有多个,输出最靠前的那个位置)

题解

之前 Picks 讲课的时候提到了这样一道题,但没说来源,所以我一直不知道网上有,后来乱逛时发现了这道题,做了一下
题解放在这篇文章的 T1 那里了
这里稍微讲一下模数为奇素数的二次剩余,使用 Cipolla 算法求解
现在要解决一个问题,给定 $n$ ,要求出模意义下的 $x$ 使
$$ x^2\equiv n\pmod{p} $$
或者说求 $\sqrt{n}\pmod{p}$
这里只是简要讲解,更详细的请到引用资料里看
继续阅读