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

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

环节长度。

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

这里只说做法

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

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

暴力求循环节[……]

Read more

二次剩余(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}|
=简化剩余系的元素个数

[……]

Read more