标签 - 二次剩余

? 解题记录 ? ? 杂OJ ? ? 二次剩余 ?    2018-12-19 19:15:49    368    0    0
The number x is called a square root of a modulo n (root( a, n)) if x* x = a (mod n). Write the program to find the square root of number a by given modulo n. Input One number K in the first line is an amount of tests ( K ≤ 100000). Each next line represents separate test, which contains inte
? 解题记录 ? ? BZOJ ? ? 二次剩余 ? ? BSGS ?    2018-12-19 10:52:32    566    0    0
Description Fib数列为1,1,2,3,5,8... 求在Mod10^9+9的意义下,数字N在Fib数列中出现在哪个位置 无解输出-1 Input 一行,一个数字N,N < = 10^9+9 Output 如题 Sample Input 3 Sample Output 4 109+910^9+9明示55有二次剩余。 考虑FibFib的通项公式: fn=1√5((1+√52)n−(1−√52)n) f_n=\frac{1}{\sqrt 5}\left (\left (\frac{1+\sqrt 5}{2}\