三次剩余

三次剩余

51nod 1039
求\(x^3\equiv a(\% P)\)
1.\(a=0\)或者\(p\leq 3\),\(res=a\)。
2.\(p \% 3 \neq 1\),\(res=a^{\left \lfloor \frac{2p-1}{3} \right \rfloor}\)。
3.剩下的情况不满足\(a^{\left \lfloor \frac{p-1}{3} \right \rfloor}\equiv 1(\% p)\)则无解。
4.随机一个\(u\{ x,y,z\} \in \Re\),\(v=u^{\frac{p-1}{3}}\)。若仅有\(v.y\neq 0\),\(v.y\)模\(p\)意义下的逆元就是其中一组答案。
设\(\epsilon = \frac{-1+\sqrt{-3}}{2}\),即\(\epsilon ^3\equiv 1(\% p)\).
\(a_1=(x_1,y_1\epsilon ,z_1\epsilon ^2)\),\(a_2=(x_2,y_2\epsilon ,z_2\epsilon ^2)\)。
\(a_1\cdot a_2\)有\(x=x_1x_2+y_1z_2+z_1y_2\)同理其他。