二次剩余

问题： 给定初始项 \( F_0, F_1 \)，满足递推关系 \( F_n = a F_{n-1} + b F_{n-2} \)，求 \( F_n \pmod p \) 的循环节长度。 原理见广义Fibonacci数列找循环节 这里只说做法 我们先写出递推式的特征式子 x^2 =ax + b，整理得到 x^2-ax-b=0，求出 delta = a^2+4b

题意： # 给定一个 N∗N(N≤4e9) 的矩阵，现在经过这样一个变换：将 (x,y) 变为 ((x+y)%N,(x+2×y)%N)(0≤x<N,0≤y<N) 现在求经过多少次这样的变换之后在回到 N∗N 的原始矩阵。

题目链接 题意：f[0] = 1,f[1] = 1,f[i] = f[i-1] + f[i-2] (i>=2)，问最小的m满足f[n]%p==f[n+m]%p 思路：求斐波那契数列循环节。 参考了Acdreamer的博客_Fib数模n的循环节

先放资料。 前置技能点： # 剩余系 剩余系**:设模为m,则根据余数可将所有的整数分成m类，分别记成[0],[1],[2],…[m-1]****，**