Uva11582 [fast power]colossal Fibonacci numbers!

The question ：f[] For fiboracci series , I want you to ask f[a^b]%n;

Ideas ： Using the nature of fiboracci , Find the cyclic section of the remainder , if f[i]==1&&f[i-1]==0, Then the cycle section is i-1;

seek a^b With a fast power

notes ：UVAunsigned long long Input and output with %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;
}