hdu 2814 Interesting Fibonacci

点击此处即可传送 hdu 2814
题目大意：就是给你两个函数，一个是F(n) = F(n-1) + F(n-2),
F(0) = 0, F(1) = 1;
另一个是 G(n) = G(n-1)^F(a^b);
G(1) = F(a^b);
求G(n) % c;
范围：A, B, N, C (10<=A, B<2^64, 2<=N<2^64, 1<=C<=300)

注意了：c的范围是1<= C <= 300,所以说它一定会有循环 节：
解题思路： 首先算G(1) = F(a^b),设a^b的循环节是len;
F（a^b）%c = F(a^b%len)%c;
一边加一边取余

然后算G(n)%c = F(a^b)^(F(a^b)^(n-1)) % c;
G(n)%c = F(a^b)^(F(a^b)^(n-1)%phi(c)+phi(c))%c;
F(a^b)^(n-1)%phi(c)+phi(c) == (F(a^b)%phi(c)^(n-1))+phi(c)
F(a^b)%phi(c) 有循环节，同上，具体详见代码

上代码：

/*
2015 - 8 - 16 下午
Author: ITAK

今日的我要超越昨日的我，明日的我要胜过今日的我，
以创作出更好的代码为目标，不断地超越自己。
*/
#include <iostream>
#include <cstdio>

using namespace std;

//快速幂取余
int quick_mod(int a, unsigned long long b, int c)
{
    int ans = 1;
    a %= c;
    while(b)
    {
        if(b & 1)
            ans = (ans*a) % c;
        b >>= 1;
        a = (a*a) % c;
    }
    return ans;
}
//欧拉函数
int Phi(int m)
{
    int ans = m;
    for(int i=2; i*i<=m; i++)
    {
        if(m%i == 0)
            ans -= ans/i;
        while(m%i == 0)
            m /= i;
    }
    if(m > 1)
        ans -= ans/m;
    return ans;
}
//公式：x^y % c == x^(y%phi(c)+phi(c))%c;
int data[90005],data1[90005];
int main()
{
    //注意不要用long long,用unsigned long long
    unsigned long long a, b, n;
    int c, c1, t, n1, n2, tmp;
    int g[10], len=0, len_c=0, len_e=0;
    scanf("%d",&t);
    for(int k=1; k<=t; k++)
    {
        //cin>>a>>b>>n>>c;
        scanf("%lld%lld%lld%d",&a,&b,&n,&c);
        if(c == 1)
        {
            printf("Case %d: 0\n",k);
            continue;
        }
        data[0]=0, data[1]=1;
        data1[0]=0, data1[1]=1;
        for(int i=2; i<90005; i++)
        {
            data[i] = (data[i-1]+data[i-2])%c;
            if(data[i]==1 && data[i-1]==0)
            {
                len = i-1;//c的循环节
                break;
            }
        }
        c1 = Phi(c);
        if(c1 > 1)
        {
            for(int i=2; i<90005; i++)
            {
                data1[i] = (data1[i-1]+data1[i-2])%c1;
                if(data1[i]==1 && data1[i-1]==0)
                {
                    len_c = i-1;//Phi(c)的循环节
                    break;
                }
            }
        }

        n1 = quick_mod(a%len, b, len);
        g[1] = data[n1];
        if(c1 == 1)
            g[2] = 0;
        else
        {
            n2 = quick_mod(a%len_c, b, len_c);
            g[2] = data1[n2];
        }
        int ans1 = quick_mod(g[2], n-1, c1);
        int ans = quick_mod(g[1], ans1+c1, c);
        if(n == 1)
            printf("Case %d: %d\n",k,g[1]);
        else
            printf("Case %d: %d\n",k,ans);
    }
    return 0;
}