斐波拉契
在OI简单数论中 斐波拉契是常常出现的东西
|是什么
斐波那契数列，又称黄金分割数列、因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=1，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用.
(百度百科)
|模板
1,递归
inline int Fib(int n)
{
if (n == 1 || n == 2)
{
return 1;
}
return Fib(n - 1) + Fib(n - 2);
}复杂度分析
由于对于每一个1都是最后一层递归返回上来的故会递归F(n)次 , 由于斐波拉契数列是随着指数上升的 故复杂度约为O(2^n)
2,循环
inline int Fib(int n)
{
F[1] = F[2] = 1;
for(int i = 3 ; i <= n ; ++ i)
F[i] = F[i - 1] + F[i - 2];
return F[n];
}复杂度分析 :O(n)
3,矩阵乘法优化
讲数列放在矩阵乘法中会发现
即如果求F[n]
将
拓展到2 * 2即
#include <iOStream>
#include <cstdio>
#include <cstring>
#define inc(i) (++ i)
#define int long long
using namespace std;
const int Mod = 1000000000 + 7;
struct JX
{
int a[3][3];
friend JX operator * (JX a , JX b)
{
JX c;
memset(c.a , 0 , sizeof(c.a));
for(int i = 1 ; i <= 2 ; inc(i))
for(int j = 1 ; j <= 2 ; inc(j))
for(int k = 1 ; k <= 2 ; inc(k))
c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j]) % Mod;
return c;
}
}Ans , A;
int n;
inline void KSM()
{
int p = n - 2;
while(p)
{
if(p & 1) Ans = Ans * A;
p >>= 1 , A = A * A;
}
}
signed main()
{
scanf("%ld" , &n);
if(n <= 2) putchar(49);
else
{
Ans.a[1][1] = A.a[1][1] = 1;//直接跳到n = 2时的矩阵
Ans.a[1][2] = A.a[1][2] = 1;
Ans.a[2][1] = A.a[2][1] = 1;
KSM();
printf("%lld" , Ans.a[1][1]);
}
return 0;
}
4, 算不上什么优化的优化(斐波拉契数列膜p的循环节)
转自Fib数模n的循环节(代码原创)
我们知道Fibonacci数列，现在我们来求一个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。
那么我们可以先求出所有的因子，然后用矩阵快速幂来一个一个判断，这样时间复杂度不会很大。
模板代码：(巨丑 见谅)
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>
#include <algorithm>
#define int long long
#define inc(i) (++ i)
#define dec(i) (-- i)
using namespace std;
const int N = 100000 + 7;
int n , Prime[N + 7] , tot , Pri[N] , Cnt[N] , cnt , TOT;
int Factor[N] , P;
bool No_Prime[N + 7];
struct JX
{
int a[4][4];
friend JX operator * (JX a , JX b)
{
JX c;
memset(c.a , 0 , sizeof(c.a));
for(int i = 1 ; i <= 2 ; inc(i))
for(int j = 1 ; j <= 2 ; inc(j))
for(int k = 1 ; k <= 2 ; inc(k))
c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j] % P) % P;
return c;
}
}A , X;
inline JX KSM_2(JX a , int q , int P)
{//矩阵优化斐波拉契数列
JX Ans = X , x = a;
while(q)
{
if(q & 1) Ans = Ans * x;
q >>= 1 , x = x * x;
}
return Ans;
}
inline void Get_Prime()
{//得出质数便于之后分解质因数
No_Prime[1] = 1;
for(int i = 2 ; i <= N ; inc(i))
{
if(!No_Prime[i]) Prime[inc(tot)] = i;
for(int j = 1 ; j <= tot && i * Prime[j] <= N ; inc(j))
{
No_Prime[i * Prime[j]] = 1;
if(i % Prime[j] == 0) break;
}
}
}
inline void resolve(int n , int Pri[] , int Cnt[])
{//分解质因数 , pri存质因子 , cnt存次数
cnt = 1;
int t = sqrt(n) , TOT;
for(int i = 1 ; Prime[i] <= t ; inc(i))
if(n % Prime[i] == 0)
{
TOT = 0;
Pri[cnt] = Prime[i];
while(n % Prime[i] == 0)
{
n /= Prime[i];
inc(TOT);
}
Cnt[cnt] = TOT;
inc(cnt);
}
if(n ^ 1)
{
Pri[cnt] = n , Cnt[cnt] = 1;
inc(cnt);
}
dec(cnt);
}
inline int KSM_1(int x , int q , int P)
{//普通的快速幂
int Ans = 1;
x %= P;
while(q)
{
if(q & 1) Ans = Ans * x % P;
q >>= 1 , x = x * x % P;
}
return Ans;
}
inline void Work(int n)
{//求n的因数
TOT = 0;
int t = sqrt(n);
for(int i = 1 ; i <= t ; inc(i))
{
if(n % i == 0)
{
if(i * i == n) Factor[inc(TOT)] = i;
else
{
Factor[inc(TOT)] = i;
Factor[inc(TOT)] = n / i;
}
}
}
}
inline int Gcd(int a , int b)
{
return a % b == 0 ? b : Gcd(b , a % b);
}
inline int Find_Loop(int n)
{
Resolve(n , Pri , Cnt);
int Ans = 1 , loop;
for(int i = 1 ; i <= cnt ; inc(i))
{
loop = 1;
P = Pri[i];
switch(P)
{
case 2: loop = 3; break;
case 3: loop = 8; break;
case 5: loop = 20; break;
default :
{
if(KSM_1(5 , (P - 1) >> 1 , P) == 1)
Work(P - 1);
else
Work(2 * (P + 1));
sort(Factor , Factor + TOT + 1);
for(int j = 1 ; j <= TOT ; inc(j))
{
JX B = KSM_2(A , Factor[j] - 1 , P);
int x = (B.a[1][1] + B.a[1][2]) % P;
int y = (B.a[2][1] + B.a[2][2]) % P;
if(x == 1 && y == 0)
{
loop = Factor[j];
break;
}
}
}break;
}
loop *= KSM_1(P , Cnt[i] - 1 , 9223372036854775807);
if(loop < Ans) swap(loop , Ans);
Ans = Ans / Gcd(loop , Ans) * loop;
}
return Ans;
}
inline int Mod(char* a , int b)//高精度a除以低精度b
{
int d = 0 , l = strlen(a);
for(int i = 0 ; i < l ; inc(i)) d = (d * 10 + (a[i] - '0')) % b;//求出余数
return d;
}
char pp[30000007];
signed main()
{
A.a[1][1] = A.a[1][2] = A.a[2][1] = 1;
X.a[1][1] = X.a[2][2] = 1;
Get_Prime();
scanf("%s%lld" , pp , &n);
int loop = Find_Loop(n);
int Ans = Mod(pp , loop);
if(!Ans) Ans = loop;
if(Ans <= 0) putchar(48);
else
if(Ans <= 2) printf("%lld" , 1ll % n);
else
{
A.a[1][1] = A.a[1][2] = A.a[2][1] = 1;
X.a[1][1] = X.a[2][2] = 1;
P = n;
X = KSM_2(A , Ans - 1 , n);
printf("%lld" , X.a[1][1]);
}
return 0;
}