首页 > 代码库 > hdu-2814-Interesting Fibonacci-斐波那契循环节

hdu-2814-Interesting Fibonacci-斐波那契循环节

哇塞,我竟然2A了。。。。没有1A纯粹是脑残了。。

求:F(a^b)^(F(a^b) ^ (n-1))%c 
既是求F(a^b)^(F(a^b) ^ (n-1)%phi[c]+phi[c])%c
先求x=F(a^b)%phi[c],有循环节,直接找到循环节就OK。
然后求y=F(a^b)%c,同求x,循环节。
然后问题就变成求y^(x^(n-1)%phi[c]+phi[c])
直接套两次快速幂取模就OK。

#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define LL unsigned __int64
#define lcm(a,b) (a*b/gcd(a,b))
//O(n)求素数,1-n的欧拉数
#define N 110000
struct math_use
{
    LL euler(LL x)
    {
        LL i, res = x;
        for (i = 2; i*i <= x; i++)
            if (x%i == 0)
            {
                res = res / i*(i - 1);
                while (x%i == 0)
                    x /= i;
            }
        if (x > 1)
            res = res / x*(x - 1);
        return res;
    }
//a^b%c
    LL q_mod(LL a,LL b,LL n)
    {
        LL ret=1;
        LL tmp=a;
        while(b)
        {
            //基数存在
            if(b&0x1) ret=ret*tmp%n;
            tmp=tmp*tmp%n;
            b>>=1;
        }
        return ret;
    }
} M;
int smod[330];
int eur[330];
LL s_mod(int mod)
{
    LL a1,a2,a3,tmp;
    a1=0;
    a2=1;
    a3=1;
    LL ans=1;
    while(a2!=0||a3!=1)
    {
        tmp=(a2+a3)%mod;
        a2=a3;
        a3=tmp;
        ans++;
    }
    return ans;
}
void init()
{
    smod[1]=1;
    eur[1]=M.euler(1);
    for(int i=2; i<=300; i++)
    {
        smod[i]=s_mod(i);
        eur[i]=M.euler(i);
    }
}
LL get_fib(int x,int mod)
{
    if(x==0)return 0;
    LL a1,a2,a3,tmp;
    a1=0;
    a2=a3=1;
    x--;
    while(x--)
    {
        tmp=(a2+a3)%mod;
        a2=a3;
        a3=tmp;
    }
    return a2;
}
LL fib(LL a,LL b,LL mod)
{
    LL ans=1;
    int yu=smod[mod];
    LL s=M.q_mod(a%yu,b,yu);
    return get_fib(s,mod);
}
int main()
{
    LL a,b,n,c;
    init();
    LL T;
    cin>>T;
    int cas=0;
    while(T--)
    {
        cas++;
        cin>>a>>b>>n>>c;
        if(c==1)
        {
            printf("Case %d: 0\n",cas);
            continue;
        }
        LL x,y;
        LL mod,mod1;
        mod=c;
        mod1=eur[c];
        x=fib(a,b,mod1);
        y=fib(a,b,mod);
        LL p=M.q_mod(x,(n-1)%eur[mod1]+eur[mod1],mod1);
        LL ans=M.q_mod(y,p+mod1,mod);
        printf("Case %d: ",cas);
        cout<<ans<<endl;
    }
    return 0;
}