UVA 11582 Colossal Fibonacci Numbers!(数论) - c++编程基础

题意：输入两个非负整数a、b和正整数n（0<=a,b<=2^64,1<=n<=1000），让你计算f（a^b）对n取模的值，其中f（0） = 0，f（1） = 1；且对任意非负整数i，f（i+2）= f（i+1）+f（i）。

思路：因为斐波那契序列要对n取模，余数只有n种，所以最多n^2项序列就开始重复，所以问题转化成了求周期然后大整数取模。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
              #include
              
                #include
               
                 #define eps 1e-6 #define LL long long #define ULL unsigned long long #define pii (pair
                
                 ) //#pragma comment(linker, /STACK:1024000000,1024000000) using namespace std; const int maxn = 1000 + 100; //const int INF = 0x3f3f3f3f; ULL a, b; int n; int f[maxn*maxn]; ULL pow_mod(ULL a, ULL p, ULL n) { if(p == 0) return 1; ULL ans = pow_mod(a, p/2, n); ans = ans * ans % n; if(p%2 == 1) ans = ans * a % n; return ans; } int main() { //freopen(input.txt, r, stdin); int T; cin >> T; while(T--) { cin >> a >> b >> n; f[0] = 0, f[1] = 1%n; int loop = 1; for(int i = 2; i <= n*n+100; i++) { f[i] = (f[i-1]+f[i-2]) % n; if(f[i]==f[1] && f[i-1]==f[0]) { loop = i - 1; break; } } ULL ans = pow_mod(a%loop, b, (ULL)loop); cout << f[ans] << endl; } return 0; }