UVa11582 - Colossal Fibonacci Numbers! （快速幂取模）

阳光穿透心脏的1/2处 2022-06-08 09:28 169阅读 0赞

输入两个非负数 a，b，和正整数n，计算f（a^b）除以n的余数；  
f（i+2） = f（i+1） + f（i）;  
函数f里是一个斐波那契数， 所以需要打表，但是由于数据太大，只能取模后存储  
因为每次n都不一样，所以每次都需要重新打表。

**先说打表：**  
当取完模后，数字都是在0到n-1徘徊，当连续两个数字与开头两个数字一样的时候，就开始了循环，（规律），例如n=3的时候，前10项为1，1，2，0，2，2，1，0，1，1，在9，10项就开始了循环，那么多久会出现重复呢，因为余数有n种，最多n^2项就会出现重复，在打表的时候注意吧周期给记录下来，以便以后取模用。

**再说快速幂：**

int pow_mod(int a, int n, int m) { // 快速幂，分治法 
        if(n == 0) return 1;
        int ans = pow_mod(a, n/2, m);
        ans = ans * ans % m;
        if(n % 2 == 1) ans = ans * a % m;
        return ans;
    }

里面的int可以用其他整形代替。  
利用二分的思想，加快运算，其中判定是否是奇数次方，然后最后乘上；

f（x） = y

**总结：这道题要求求余数，即知x求y%n，我们利用其中的规律性–周期，发现y%n之后是有规律的(y是斐波那契数)，设T为周期的话，我们只需要知道x%T就可以了，因为y%n一直在循环，所以转为去求a^b%n的值，利用快速幂就轻松求得。**  
下面是代码：

#include<iostream>
    #include<cstring>
    #define MAXN 1000
    #define ULL unsigned long long //比long long 长 
    
    using namespace std;
    
    int vis[1010000];
    int p;
    
    void init(int n) {
        vis[0] = 0, vis[1] = 1%n; //取模，关系着周期 
        for(int i = 2; i <= n*n+100; i++) {
            vis[i] = (vis[i-1] + vis[i-2]) % n;
            if(vis[i] == vis[1] && vis[i-1] == vis[0]) {
                p = i - 1;//记录周期 p 
                break;
            }   
        }
    }
    
    ULL pow_mod(ULL a, ULL n, ULL m) { // 快速幂，分治法 
        if(n == 0) return 1;
        ULL ans = pow_mod(a, n/2, m);
        ans = ans * ans % m;
        if(n % 2 == 1) ans = ans * a % m;
        return ans;
    }
    
    int main() {
        int t, n;
        ULL c1, c2;
        cin >> t;
        while(t--) {
            cin >> c1 >> c2 >> n;
            init(n);
            printf("%d\n", vis[pow_mod(c1%p, c2, (ULL)p)]);
        } 
        return 0;
    }