[BSGS算法]纯水斐波那契数列

学弟在OJ上加了道“非水斐波那契数列”求斐波那契第n项对1,000,000,007取模的值n

学弟在OJ上加了道“非水斐波那契数列”求斐波那契第n项对1,000,000,007取模的值n<10^15随便水过后我决定加一道升级版说是升级版其实也没什么变化只不过改成n<10^30000000并对给定p取模0

下面来简单介绍一下BSGS算法BSGSBaby steps and giant steps又称包身工树大步小步法听上去非常高端其实就是一个暴力搜索。比如我们有一个方程a^x≡b (mod c)x是未知数怎么算难道是什么神奇的数学公式直觉和经验告诉我们这玩意儿并不好算无奈的我们只好枚举x欧拉dalao告诉我们a^φ(c)≡1 (mod c)再怎么不济我们O(c)也能算出答案……平时我们常见的模数一般都有十亿左右明显要T啦怎么办

别急我们来回顾一个经典问题给你有n个数的集合问他有多少个子集和为x。(n<100,000x<10^18)

别想了我也不会做只好把数据改一改n<20暴力就过啦。n<50此时有个常见的做法我们枚举前n/2个数的和开个map存下再枚举后n/2个数用x减掉枚举出的和再去map里找……复杂度O(2^(n/2))可能还要多个log。我们再考虑下子集积发现并没有区别枚举前n/2个数的积存下再枚举后n/2个数用x乘上枚举出的积的逆元假设取模……是不是想到了什么我们像快速幂那样把a^x表示成a^1,a^2,a^4,a^8……的积解那个方程不就是做子集积吗实际上不用这么麻烦我们把x表示成只有两位的k进制数我们就只要枚举两位了令xAkB则a^(AkB)≡b (mod c)移项得a^Ak≡b*a^-B (mod c)我们先枚举A算出等式左边存入map里再枚举B算出等式右边去map里找就能算出答案啦。要保证这个k进制数只有两位k自然大约是c^0.5。实际上我们可以稍微把k改大一点或者A多枚举一点把x改成xAk-B这样有什么好处呢你代回去再移一次项就会发现我们不用算逆元啦于是我们得到一个较为高效的求解指数方程的算法复杂度大概是O(c^0.5)视具体实现可能会多个log。

好了我们回到斐波那契数列10^30000000明显就算我们用某klogklogn的算法也不是很好受纯属口胡。实际上很容易想到斐波那契对一个数取模必然有循环节因为每一项只和前两项有关两项数的取值最多p^2种p为模数所以循环节至多p^2。事实上某篇论文证明了斐波那契数列对p取模的循环节不会超过6p其实论文中还给出了对于不同的p循环节的计算方法不过复杂度应该和接下来要讲的BSGS做法相同(理论上论文做法更优但我们肯定不想总依靠玄学的论文吧)有兴趣的可以百度一下。那么我们如何用BSGS算出循环节呢假设斐波那契数列的递推矩阵为A我们只要求出A^x≡A (mod p)的一个大于1的解就可以了求解过程和整数方程并没有太大区别。求出循环节后把那巨长无比的数字串取模下随便水过该题。

以下是加了一些奇怪的常数优化的代码……如果看的时候遇到一些不知道在干嘛的地方跳过就好了。

#include#include#includeusing namespace std;#define ll long long#define MN 30000050#define K 115000char s[MN5];int mod;struct mat{ int z[2][2]; mat(){memset(z,0,sizeof(z));} mat operator*(mat b) { mat c;int i,j,k; for(i0;i<2;i)for(j0;j<2;j) for(k0;k<2;k)c.z[i][j](c.z[i][j](ll)z[i][k]*b.z[k][j])%mod; return c; } friend bool operator<(mat a,mat b) { for(int i0;i<2;i)for(int j0;j<2;j) { if(a.z[i][j]b.z[i][j])return false; } }}f,k,p;mat pow(ll x){ mat rf,tf; for(--x;x;x>>1,tt*t)if(xr*t; return r;}map mp;int main(){ int i,l,r,mid;ll x,x1,x2,x3,x4,rp; f.z[0][1]f.z[1][0]f.z[1][1]1; fread(s,1,MN,stdin); for(l1,rMN;l>1])lmid1; else imid,rmid-1; while(s[--i]9)s[i]0; while(s[i]>09)--i; for(li;s[l]9;)s[l--]0; while(s[i]>09)mod(mod<<3)(mod<<1)s[i]-0,s[i]0; for(pkpow(K),i2;i 正常版

#include#include#includeusing namespace std;#define ll long long#define MN 30000000#define K 115000char s[MN5];int mod;struct mat{ int z[2][2]; mat(){memset(z,0,sizeof(z));} mat operator*(mat b) { mat c;int i,j,k; for(i0;i<2;i)for(j0;j<2;j) for(k0;k<2;k)c.z[i][j](c.z[i][j](ll)z[i][k]*b.z[k][j])%mod; return c; } friend bool operator<(mat a,mat b) { for(int i0;i<2;i)for(int j0;j<2;j) { if(a.z[i][j]b.z[i][j])return false; } }}f,k,p;mat pow(ll x){ mat rf,tf; for(--x;x;x>>1,tt*t)if(xr*t; return r;}map mp;int main(){ int i;ll x,rp; f.z[0][1]f.z[1][0]f.z[1][1]1; scanf("%s%d",s, for(pkpow(K),i2;i 

转载于:https://www.cnblogs.com/ditoly/p/BSGS-Fibonacci.html