https://vjudge.net/problem/UVA-11582
首先明确，斐波那契数列在模c的前提下是有循环节的。而f[i] = f[i-1]+f[i-2](i>=2)所以只要有两个连续的值和开头的一样，后面就开始循环，两两组合共有c*c种。
找到循环节之后
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cstdlib> 6 #include<string> 7 #include<cmath> 8 #include<vector> 9 #include<stack> 10 #include<set> 11 #include<iterator> 12 #include<queue> 13 #include<cctype> 14 #include<map> 15 #define lson l, m, rt<<1 16 #define rson m+1, r, rt<<1|1 17 #define IO ios::sync_with_stdio(false);cin.tie(0); 18 #define INF 0x3f3f3f3f 19 #define MAXN 100010 20 const int MOD=1e9; 21 typedef unsigned long long ll; 22 using namespace std; 23 ll t, a, b, c, M; 24 ll f[1000010]; 25 ll mod_pow(ll a, ll b, ll c) 26 { 27 ll r = a, ans=1; 28 while(b){ 29 if(b&1){ 30 ans = (ans*r)%c; 31 } 32 r = (r*r)%c; 33 b >>= 1; 34 } 35 return ans; 36 } 37 int main() 38 { 39 cin >> t; 40 while(t--){ 41 M=0; 42 cin >> a >> b >> c; 43 f[0] = 0; f[1] = 1; 44 if(c==1){//c=1的话进不了下面的循环，特判 45 cout << "0" << endl; 46 } 47 else{ 48 for(int i = 2; i <= c*c; i++){//模c，余数有c种可能，两两组合有c*c种 49 f[i] = (f[i-1]%c+f[i-2]%c)%c; 50 if(f[i-1]==f[0]&&f[i]==f[1]){//找到循环节 51 M = i-1;//循环个数 52 break;//实际比预想的小很多，break跳出循环 53 } 54 } 55 cout << f[mod_pow(a%M, b, M)] << endl;//a是index 56 } 57 } 58 return 0; 59 }