UVA 11582 巨大的斐波那契额数列！快速幂取模-白红宇

UVA 11582 巨大的斐波那契额数列！快速幂取模

阅读量：5815 次

发布时间：2019-06-18

本文共 1083 字，大约阅读时间需要 3 分钟。

从现在开始做紫皮书上的题，本题是一道斐波那契数列的题，结合快速幂，水题。

输入a, b, n, 计算f( a ^ b) % n ， f( i ) = f( i - 1) + f( i - 2 ) ， f( 0 ) = f(1) = 1, 其中，0 <= a , b <= 2 ^ 64, 0 <= n <= 1000

以后少废话，直接存代码

// 计算 f(a^b) mod n, 其中 f(i) = f(i-1) + f(i-2), f(0) = f(1) = 1, 其中0 <= a, b < 2^64 , n <= 1000#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define MAXN 1007typedef unsigned long long LL;int f[MAXN*MAXN];int fun( LL a, LL b, int n ) {    LL ans = 1;    a = a % n;    while( b > 0 ) {        if( b & 1 ) ans = ans * a % n;        b /= 2;        a = a * a % n;            }    return (int)ans;}int main() {    LL a, b;    int n;    int t;    cin >> t;    while( t-- ) {        cin >> a >> b >> n;        memset( f, 0, sizeof(f) );        f[0] = f[1] = 1;        int i = 0;                for( i = 2; i <= n * n; i++ ) {            f[i] = ( f[i-1] % n + f[i-2] % n ) % n;        }                cout << f[fun( a, b, n )-1] << endl;    }    }