UVa11582 [快速幂]Colossal Fibonacci Numbers!

题意：f[]为斐波拉契数列，要你求f[a^b]%n;

思路：利用斐波拉契的性质，找余数的循环节，若f[i]==1&&f[i-1]==0,则循环节为i-1；

求a^b用快速幂

注：UVAunsigned long long输入输出用 %llu

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
ull qpow(ull a,ull b,ull cnt)
{
    a=a%cnt;
    ull ans=1;
    while(b>0)
    {
        if(b%2==1)
            ans=a*ans%cnt;
        b/=2;
        a=a*a%cnt;
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ull a,b,n;
        scanf("%llu%llu%llu",&a,&b,&n);
        ull i;
        vector<ull>fib;
        fib.push_back(0);
        fib.push_back(1);
        ull cnt=0;
        for(i=2;i<=n*n;i++)
        {
            fib.push_back((fib[i-1]+fib[i-2])%n);
            cnt++;
            if(fib[i]==1&&fib[i-1]==0)
                break;
        }
        if(n!=1)
        printf("%llu\n",fib[qpow(a,b,cnt)]);
        else printf("0\n");
    }
    return 0;
}