首页 > 代码库 > UVA 11582 Colossal Fibonacci Numbers!

UVA 11582 Colossal Fibonacci Numbers!

2024-07-15 07:43:25   221人阅读

斐波那契数列。。。

利用斐波那契数列的循环：因为结果%n，所以最多有n^2个数后会出现循环。

预处理，不能直接用f[maxn][maxn^2]来保存，数组太大。。。

所以用vector来保存斐波那契数列%n 的值。

 

 

 

 1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 #include <algorithm> 6 #include <vector> 7 #include <queue> 8 using namespace std; 9 10 typedef unsigned long long ll;11 12 const int maxn=1005;13 14 ll pow_mod (ll a,ll b,int n){15     ll ans=1;16     while (b){//cout<<b<<endl;17         if (b&(ll)1)18             ans=(ans*a)%n;19         a=(a*a)%n;20         b>>=1;21     }22     return ans;23 }24 25 vector<int> f[maxn];26 27 void init (){28     for (int mod=2;mod<maxn;mod++){29         int a,b,c;30         a=0;b=1;c=(a+b)%mod;31         f[mod].push_back (a);32         f[mod].push_back (b);33         f[mod].push_back (c);34         while (!(b==0&&c==1)){35             a=b;b=c;c=(a+b)%mod;36             f[mod].push_back (c);37         }38         f[mod].pop_back ();39         f[mod].pop_back ();40         //cout<<mod<<":"<<f[mod].size()<<"    ";41     }42 }43 44 int main (){45     int t,n;46     ll a,b;47     init ();48     cin>>t;49     //scanf ("%d",&t);50     while (t--){51         cin>>a>>b>>n;52         //scanf ("%lld%lld%d",&a,&b,&n);                //cout<<a<<" "<<b<<" "<<n<<"ee";53         if (n==1){54             printf ("0\n");55             continue ;56         }57         ll ans;58         int mod;59         mod=f[n].size();60         ans=pow_mod (a%mod,b,mod);//cout<<mod<<endl;61         //printf ("%d\n",f[n][ans%mod]);62         cout<<f[n][ans%mod]<<endl;63     }64     return 0;65 }

 


联系
我们