广义Fibonacci数列找循环节 (二次剩余)

问题:给定,满足,求的循

环节长度。

原理见广义Fibonacci数列找循环节

这里只说做法

我们先写出递推式的特征式子   x^2 =ax + b,整理得到 x^2-ax-b=0求出 delta = a^2+4b

对于质因数小于等于delta的部分,我们选择暴力求循环节。

暴力求循环节的代码如下:

通常做法是先暴力求出来之后,写进一个表里。

通常不会有很多项。

对于质因数大于delta的部分,我们判断每个质因数是否是delta的二次剩余,如果是,枚举(prime-1)的因子,否则枚举2*(prime+1)的因子。

贴一个板子,需要注意如果是多个函数嵌套的形式,我们只需要从外向里,依次求循环节即可。

 

再补一个,更为常用的,求斐波那契循环节的板子:

 

hdu 4794 Arnold (二次剩余,斐波那契循环节)

题意:

给定一个 NN(N4e9) 的矩阵,现在经过这样一个变换:将 (x,y) 变为 ((x+y)%N,(x+2×y)%N)(0x<N,0y<N) 现在求经过多少次这样的变换之后在回到 NN 的原始矩阵。

思路:

在模n的剩余系下可以写成(fib(n)x+fib(n+1)y,fib(n+1)x+fib(n+2)y)的形式fib(n)表示Fibonacci数列的第n项

所以就成了斐波那契数列循环节。。经典题。注意会爆long long,要用ULL

又写了遍板子,去年的东西都忘得差不多了orz

 

 

hdu 3977 Evil teacher (斐波那契数列循环节)

题目链接

题意: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数模素数的最小循环节长度。可以看出我们现在最重要的就是求

对于求我们利用如下定理:

   如果5是模的二次剩余,那么循环节的的长度是的因子,否则,循环节的长度是的因子。

顺便说一句,对于小于等于5的素数,我们直接特殊判断,loop(2)=3,loop(3)=8,loop(5)=20。

那么我们可以先求出所有的因子,然后用矩阵快速幂来一个一个判断,这样时间复杂度不会很大。

这道题是模板题。博客中的模板代码很好理解…

换成了自己比较熟悉的矩阵构造方式,以及代码风格。

需要注意的是下标是从0开始的,当验证k是否为循环节的时候,应该验证f[k]和f[k+1]

 

 

 

二次剩余(Cipolla’s algorithm)学习笔记

先放资料。


 

前置技能点:
剩余系

剩余系:设模为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互素代表元构成简化剩余系。
当m=10则,{0,1,2,3,4,5,6,7,8,9} 完全剩余系
{1,3,7,9}是简化剩余系(x,10)=1
当m=5则,{0,1,2,3,4}为完全剩余系,
{1,2,3,4}是简化剩余系,因为除去余0(正好是倍数)外,其它都互素。
f(m)=欧拉函数=|{t|0<t<m, (t, m)=1}|
=简化剩余系的元素个数

继续阅读“二次剩余(Cipolla’s algorithm)学习笔记”