本文主要是介绍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("0\n");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
这篇关于Colossal Fibonacci Numbers! 数学的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!