Colossal Fibonacci Numbers! 数学

Colossal Fibonacci Numbers! 数学

题意：输入两个非负整数 a,b 和正整数 n （0<=a,b<2^64 , 1<=n<=1000) 求斐波拉数f(a^b)%n 的值 其中f(0)=0 f(1)=1  

分析：

斐波拉契数列规律：所有数对n取模，二元组（ f(i),f(i+1) ) 有 n*n 种组合 则必有重复 （ f(i),f(i+1) )，导致数列循环

可转化为 =>  a^b 对 循环周期time取模的问题

其中0~2^64  可用unsinged long long 类型存储 

幂取模 需要用快速幂  

即可

#include<bits/stdc++.h>
#define ll unsigned long long  
using namespace std;
pair<int,int> Pair;
vector<int > vt;
int f[10000005];
int main()
{int T;cin>>T;while(T--){ll a,b;int n;cin>>a>>b>>n;if(a==0||n==1) //特判 {printf("0n");continue;}f[0]=0;f[1]=1;f[2]=1;int time;for(int i=3;1 ;i++){f[i]=f[i-1]+f[i-2];f[i]%=n;if(f[i]%n==1&&f[i-1]%n==1){time=i-2;break;}}a%=time;ll ans=1;ll hh=a;int mod=time;while(b){hh%=mod; if(b%2) ans=ans*hh%mod;ans%=mod;hh=hh*hh%mod;			b=b/2;	}int gg=ans;if(gg==0) gg=time;cout<<f[gg]<<endl;}return 0;
}
//10
//1 1 2
//2 3 1000
//18446744073709551615 18446744073709551615 1000
//0 1 1000
//18446744073709551615 0 1
//1 0 1000
//0 18446744073709551615 1000
//7 98 500
//1 500000 1000
//1 1 1