Colossal Fibonacci Numbers! UVA - 11582

偏执的太偏执、 2022-06-15 03:23 132阅读 0赞

Think:  
1知识点:快速乘+数学规律+取模知识+64位无符号整数与64位有符号整数范围  
(有符号型64位整数，值域为：-9223372036854775808 .. 9223372036854775807;  
无符号型64位整数，值域为：0 .. 18446744073709551615)  
2题目分析:  
1>输入两个非负整数a, b和正整数n(0 <= a, b <= 2^64, 1 <= n <= 1000),计算f(a^b)%n的结果，f(0) = 0, f(1) = 1，f(i+2) = f(i+1) + f(i);  
2>所有计算都是对n取模的，可以设F(i) = f(i) % n;可以发现，当二元组(F(i), F(i+1))出现重复时候，整个序列开始出现重复.因为余数最多n中，因此最多n^2项就会出现重复。寻找周期T，然后计算出F(0)~F(n^2)(可优化只计算出F(0)~F(M)项即可)，然后算出F(a^b)等于其中的那一项即可  
3错误反思:没有仔细分析出测试数据中出现了超出64位有符号整数范围的测试数据，存储数据的变量无法存储超出64位有符号整数范围的数据进而导致测试结果一直不对

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <bits/stdc++.h>
    
    typedef unsigned long long LL;
    
    using namespace std;
    
    LL F[1040000];
    int pow_mod(LL a, LL k, int mod);
    int solve(int n);
    
    int main(){
        int T, mod, t;
        LL a, b, n;
        scanf("%d", &T);
        while(T--){
            scanf("%llu %llu %llu", &a, &b, &n);
            mod = solve(n);
            t = pow_mod(a, b, mod);
            printf("%llu\n", F[t]);
        }
        return 0;
    }
    int pow_mod(LL a, LL k, int mod){
        LL ans = 1;
        a %= mod;
        while(k){
            if(k & 1)
                ans = (ans*a) % mod;
            a = (a*a) % mod;
            k >>= 1;
        }
        return (int)ans;
    }
    int solve(int n){
        F[0] = 0, F[1] = 1 % n;
        for(int i = 2; ; i++){
            F[i] = (F[i-1] + F[i-2]) % n;
            if(F[i-1] == F[0] && F[i] == F[1]){
                return i-1;
            }
        }
    }

[vjudge]: https://vjudge.net/problem/UVA-11582