巨大的斐波那契数 uva1582

2019-04-14 20:03发布

站内文章 / 模拟电子
14432 0 1664
斐波那契数的性质：点击打开链接        数列的数模除某个数的结果会呈现一定周期性，因为数列中的某个数取决与前两个数，一旦有连着的两个数的模除结果分别等于第0 第一项的模除结果，那麽代表着一个新的周期的的开始，如果模除n，则每个周期中的元素不会超过n×n; Th 根据这个性质，不难发现当二元组（F(i),F(i+1)）出现重复时，整个序列就会开始重复，只要F(a^b)等于之前的哪一个即可。 注意一下精度，a和b均是2的64次方，会超long long,要设置成unsigned long long

代码如下： #include #include #include using namespace std; typedef unsigned long long ll; const int N=1000; vectorf[N]; void init() { f[1].push_back(0); for(int i=2;i<=N;i++) { int a=0%i,b=1%i,c; f[i].push_back(a); f[i].push_back(b); c=(a+b)%i; while(!(b==0&&c==1)) { f[i].push_back(c); a=b; b=c; c=(a%i+b%i)%i; } f[i].pop_back(); } } ll pow(ll a,ll b,int mod) { ll res=1; ll base=a%mod; while(b) { if(b&1) res=(res%mod*base%mod)%mod; base=(base%mod*base%mod)%mod; b=b>>1; } return res; } int main() { int t; ll a,b,c; int n; init(); scanf("%d",&t); while(t--) { scanf("%llu%llu%d",&a,&b,&n); if(a==b&&a==0) printf("0 "); else { c=pow(a,b,f[n].size()); printf("%d ",f[n][c]); } } return 0; }

热门文章