**问题：**给定 ，满足 ，求 的循 环节长度。 原理见广义Fibonacci数列找循环节 这里只说做法 我们先写出递推式的特征式子 x^2 =ax + b,整理得到 x^2-ax-b=0求出 delta = a^2+4b 对于质因数小于等于delta的部分，我们选择暴力求循环节。 暴力求循环节的代码如下： int get_loop( LL p) //暴力得到不大于13的素数的循环节。 { LL a,b,c; a = 0 ; b = 1 ; for ( int i = 2; ; i++) { c = (a+3*b%p)%p; //此处为递推式 a = b; b = c; if (a==0&&b==1) return …

题意： 给定一个 N∗N(N≤4e9) 的矩阵，现在经过这样一个变换：将 (x,y) 变为 ((x+y)%N,(x+2×y)%N)(0≤x<N,0≤y<N) 现在求经过多少次这样的变换之后在回到 N∗N 的原始矩阵。 思路： 在模n的剩余系下可以写成(fib(n)x+fib(n+1)y,fib(n+1)x+fib(n+2)y)的形式fib(n)表示Fibonacci数列的第n项 所以就成了斐波那契数列循环节。。经典题。注意会爆long long,要用ULL 又写了遍板子，去年的东西都忘得差不多了orz /* *********************************************** Author …

题目链接 题意：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的循环节 对于一个正整数n，我们求Fib数模n的循环节的长度的方法如下： （1）把n素因子分解，即 （2）分别计算Fib数模每个 的循环节长度，假设长度分别是 （3）那么Fib模n的循环节长度 从上面三个步骤看来，貌似最困难的是第二步，那么我们如何求Fib模 的循环节长度呢？  这里有一个优美的定理：Fib数模 的最小循环节长度等于 ，其中 表示Fib数模素数 的最小循环节长度。可以看出我们 …

先放资料。 前置技能点： 剩余系 剩余系**:设模为m,则根据余数可将所有的整数分成m类，分别记成[0],[1],[2],…[m-1]****，** 这m个数**{0,1,2,****…****m-1}**称为一个完全剩余系， 每个数称为相应类的代表元。 当m=10（偶数）时候，则{0,1,2,3,4,5,6,7,8,9}是最小非负完全剩余系 {-5,-4,-3,-2,-1,0,1,2,3,4,5} 是绝对值最小完全剩余系 {-4,-3,-2,-1,0,1,2,3,4,5} 绝对值最小 {1,2,3,4,5,6,7,8,9,10}是最小正完全剩余系 简化剩余系:在每个剩余类选取至1个与m …