計蒜客 Fib數列問題二

問題描述

用 fib(n) 表示斐波那契數列的第 n項，現在要求你求 fib(n) mod m。fib(1)=1,fib(2)=1。

輸入格式

輸入 2 個整數 n(1≤n≤10^18 )，m(2≤m≤100000000)。

輸出格式

輸出 fib(n) 對 m 取模的值。

樣例輸入

100000000 100000000

樣例輸出

60546875

方法一：疊代（該方法逾時）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cal(ll a,ll mod)
{
	int x1=1,x2=1;
	ll res=0;
	if(a==1||a==2)
	   return 1;
	for(ll i=3;i<=a;i++)
	{
		res=(x1%mod)+(x2%mod);
		res%=mod;
		x1=x2;
		x2=res;
	}
	return res;
}
int main()
{
	ll n,m;
	cin>>n>>m;
	cout<<cal(n,m)<<endl;
	return 0;
 } 
           

方法二：矩陣快速幂（一定要在最後再次取餘）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll nn=2;
struct matrix{
	ll a[100][100];
};
matrix matrix_mul(matrix A,matrix B,ll mod)
{
	matrix C;
	for(int i=0;i<nn;i++)
	{
		for(int j=0;j<nn;j++)
		{
			C.a[i][j]=0;
			for(int k=0;k<nn;k++)
			{
				C.a[i][j]+=A.a[i][k]%mod*B.a[k][j]%mod;
				C.a[i][j]%=mod;
			}
		}
	}
	return C;
}
matrix unit()
{
	matrix res;
	for(int i=0;i<nn;i++)
	{
		for(int j=0;j<nn;j++)
		{
			if(i==j)
			{
				res.a[i][j]=1;
			}
			else
			{
				res.a[i][j]=0;
			}
		}
	}
	return res;
}
matrix pow_matrix(matrix A,ll y,ll mod)
{
	matrix res=unit(),temp=A;
	for(;y;y/=2)
	{
		if(y&1)
		{
			res=matrix_mul(res,temp,mod);
		}
		temp=matrix_mul(temp,temp,mod);
	}
	return res;
}
int main()
{
	ll n,m;
	scanf("%lld%lld",&n,&m);
	if(n==1||n==2)
	{
		cout<<"1"<<endl;
		return 0;
	}
	   
	matrix A;
	A.a[0][0]=1;
	A.a[0][1]=1;
	A.a[1][0]=1;
	A.a[1][1]=0;
	matrix B=pow_matrix(A,n-2,m);
	/*for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			cout<<B.a[i][j]<<" ";
			
		}
		cout<<endl;
	}*/
	ll ans=0;
	ans=(B.a[0][0]+B.a[0][1])%m;
	printf("%lld\n",ans);
	return 0;
}