嗯...很多人应该是冲着这个标题来的
（斐波那契的魅力）
1.分析题面
点开题目，浏览一遍题目，嗯？这么简单？还是蓝题？
再看看数据范围，感受出题人深深的好意...
(n,m leq 10^9)
就算加上矩阵快速幂，(fib[1000000000]) 也不是高精度能存的下的。
所以，我们得想一点技巧。
2.寻找思路
深呼吸，思考学过的斐波那契数列的性质...（？？？）
......
终于，它出现了！
(gcd(fib[x],fib[y])=fib[gcd(x,y)])
怎么证呢？
证明：先证明斐波那契数列相邻两项是互素的。
-
反证法。若不互素，设(x=gcd(fib[i],fib[i-1]),x>1)
则(x|fib[i],x|fib[i-1])
又因为(fib[i-2]=fib[i]-fib[i-1])
所以(x|fib[i-2])
一直往前推，直到(x|fib[2])
又因为(fib[2]=1)
所以(x=1),矛盾！
接着，证明(fib[n]=fib[m] fib[n-m+1]+fib[m-1] fib[n-m])
-
(fib[n]=fib[n-1]+fib[n-2])
(fib[n]=2fib[n-2]+fib[n-3])
(fib[n]=3fib[n-3]+2fib[n-4])
...
(fib[n]=fib[m] fib[n-m+1]+fib[m-1] fib[n-m])
最后，来到了对原公式的证明：
-
(gcd(fib[x],fib[y]))
(=gcd(fib[y]fib[x-y+1]+fib[y-1]fib[x-y],fib[y]))
(=gcd(fib[x-y],f[y]))（因为(fib[y-1])与(fib[y])互质）
以此递推下去，得:
(=gcd(fib[x mod y],f[y]))
这不是辗转相除吗？以此类推，最后会得到：
(=gcd(fib[0],fib[gcd(x,y)]))
(=fib[gcd(x,y)])
呼，总算证完了~~
接下来，求(fib[i])，应该不要多讲了吧？矩阵快速幂就行了啊！
没学过的同学看这里：矩阵快速幂（原理+模板）
3.代码实现
终于来到了code time了呢~~
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=1e8;
struct Matrix{
long long matrix[105][105];
int x,y;
Matrix(const long long a[105][105],int xx,int yy){
for(int i=1;i<=xx;i++){
for(int j=1;j<=yy;j++){
matrix[i][j]=a[i][j];
}
}
x=xx,y=yy;
}
Matrix(int fill,int xx,int yy){
for(int i=1;i<=xx;i++){
for(int j=1;j<=yy;j++){
matrix[i][j]=fill;
}
}
x=xx,y=yy;
}
Matrix(){
x=y=0;
memset(matrix,0,sizeof(matrix));
}
Matrix operator*(const Matrix& a) const{
Matrix ans;
for(int i=1;i<=x;i++){
for(int j=1;j<=a.y;j++){
ans.matrix[i][j]=0;
for(int k=1;k<=y;k++){
ans.matrix[i][j]+=matrix[i][k]*a.matrix[k][j];
ans.matrix[i][j]%=mod;
}
}
}
ans.x=x,ans.y=a.y;
return ans;
}
Matrix operator%(const int& a) const{
Matrix ans;
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
ans.matrix[i][j]=matrix[i][j]%a;
}
}
return *this;
}
Matrix operator^(const long long& a) const{
Matrix ans(1,x,y),power(*this);
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
if(i!=j) ans.matrix[i][j]=0;
}
}
long long tmp=a;
while(tmp){
if(tmp&1){
ans=ans*power;
ans=ans%mod;
}
power=power*power;
tmp>>=1;
power=power%mod;
}
return ans;
}
}m;
long long n,k,p;
int t;
const long long d[105][105]={
{0,0,0},
{0,1,1},
{0,1,0}
};
Matrix c(1,2,1);
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
int main(){
Matrix m(d,2,2);
cin>>n>>p;
k=gcd(n,p);
if(k<=2) {
cout<<1<<endl;
return 0;
}
Matrix ans=c*(m^(k-1));
cout<<ans.matrix[1][1]<<endl;
return 0;
}
蒟蒻写博客不易，还请各位大佬点个赞～～