模的应用--uva11582 Colossal Fibonacci Numbers!

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

思想很巧妙，求f(a ^ b) % n，斐波那契数列极大，所以先对数列求余，得F(i) = f(i) % n，F(i)就不会超过n。

f(i) = f(i - 1) + f(i - 2),F(i) = (f(i - 1) + f(i - 2)) % n。F数列仅取决于n。f数列仅取决于每次前2项，F同理。

当F(i - 1),F(i - 2)开始重复的时候，F数列也开始重复，得周期cycle。

再找到a^b在周期中位置，即（a ^ b） % cycle，即可得答案。

ps: 2^64 是unsigned long long

pps: n为1时，F即为f，不知道为什么要输出0.

#include <iostream>

#include <cstdio>

#include <vector>

using namespace std;

int main()

{

    int t;

    cin >> t;

    int n;

    while (t --) {

        unsigned long long a,b;

        cin >> a >> b >> n;

        if(n == 1) cout << 0 << endl;

        else {

        int cycle = 0;

        vector<int> v;

        v.push_back(0),v.push_back(1),v.push_back(1);

        for (int i = 3; i < 2 * n * n; i ++) {

            v.push_back((v[i-1] + v[i - 2]) % n);

            if(v[i - 1] == 0 && v[i] == 1) {cycle = i - 1;break;}

        }

       unsigned long long res = 1;

        while (b) {

            if(b & 1) res = res * a % cycle;

            b >>= 1;

            a = ((a % cycle) * (a % cycle)) % cycle;

        }

        cout << v[res % cycle]  << endl;

        }

    }

    return 0;

}