UVa11582 - Colossal Fibonacci Numbers

UVa11582 - Colossal Fibonacci Numbers!

Problem F: Colossal Fibonacci Numbers!

The i'th Fibonacci number f (i) is recursively defined in the following way:

• f (0) = 0 and f (1) = 1
• f (i+2) = f (i+1) + f (i)  for every i ≥ 0

Your task is to compute some values of this sequence.

Input begins with an integer t ≤ 10,000, the number of test cases. Each test case consists of three integersa,b,n where 0 ≤ a,b < 2⁶⁴ (a and b will not both be zero) and 1 ≤ n ≤ 1000.

For each test case, output a single line containing the remainder of f (a^b) upon division by n.

Sample input

3
1 1 2
2 3 1000
18446744073709551615 18446744073709551615 1000

Sample output

1
21
250

利用斐波那契循环的性质！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
unsigned long long m,n;
int MOD;
vector<int> fib[1001];
void init(){
    for(int i = 2; i <= 1000; i++){
        int mod = i;
        int a = 0,b = 1,c = (a+b)%mod;
        fib[i].push_back(a);
        fib[i].push_back(b);
        fib[i].push_back(1%mod);
        while(!(b==0&&c==1)){
            a = b;
            b = c;
            c = (a+b)%mod;
            fib[i].push_back(c);
        }
        fib[i].pop_back();fib[i].pop_back();
        //cout<<fib[i].size()<<" "<<i<<endl;
    }
}
int main(){

    int ncase;
    cin >> ncase;
    init();
    while(ncase--){
        cin >> n >> m >> MOD;
        if(MOD == 1){
            cout<<0<<endl;
            continue;
        }
        int a = 0,b = 1,c = (a+b)%MOD;
        unsigned long long  mm = fib[MOD].size(),ans = 1;
        while(m){
            if(m&1)
                ans = ((n%mm)*(ans%mm))%mm;
            n = ((n%mm)*(n%mm))%mm;
            m >>= 1;

        }
        //cout<<<<endl;
        cout<<fib[MOD][ans]<<endl;

    }
    return 0;
}