hdoj5667 BestCoder Round #80 【费马小定理（膜拜）+矩阵快速幂+快速幂】

#include<cstdio>

#include<string>

#include<iostream>

#include<vector>

#include<set>

#include<map>

#include<math.h>

#include<queue>

#include<stdlib.h>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long LL;

/*

1 0 0

1 C 1

0 1 0

*/

/*费马小定理的运用【第一次，膜拜费马小定理】*/

LL n,a,b,c,p,q;

struct asd{

    LL a[5][5];

};

asd mul(asd a1,asd a2)

{

    asd ans;

    for(int i=0;i<3;i++)

    {

        for(int j=0;j<3;j++)

        {

            ans.a[i][j]=0;

            for(int k=0;k<3;k++)

            {

                ans.a[i][j]+=a1.a[i][k]*a2.a[k][j];

                ans.a[i][j]%=q;

            }

            ans.a[i][j]%=q;

        }

    }

    return ans;

}

asd quickmul(LL g,asd z)

{

    asd ans;

    for(int i=0;i<3;i++)

    {

        for(int j=0;j<3;j++)

        {

            if(i==j)

                ans.a[i][j]=1;

            else

                ans.a[i][j]=0;

        }

    }

    while(g)

    {

        if(g%2)

        {

            ans=mul(ans,z);

        }

        g/=2;

        z=mul(z,z);

    }

    return ans;

}

LL liu(LL x,LL y)

{

    LL ans;

    ans=1;

    while(y)

    {

        if(y%2)

            ans=ans*x%p;

        y/=2;

        x=x*x%p;

    }

    return ans;

}

/***---先用矩阵快速幂算出次数，然后用快速幂算出答案-----***/

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&p);

        if(n==1)

        {

            printf("1\n");

            continue;

        }

        q=p-1;

        if(a%p==0)

        {

            printf("0\n");

            continue;

        }

        asd m;

        m.a[0][0]=1;m.a[0][1]=0;m.a[0][2]=0;

        m.a[1][0]=1;m.a[1][1]=c;m.a[1][2]=1;

        m.a[2][0]=0;m.a[2][1]=1;m.a[2][2]=0;

        asd ans;

        ans=quickmul(n-2,m);    //m矩阵的(n-1)次，之后还要×一个特定矩阵 z;PS:因为算出了的已经包括了两个，然后所以是n-2...搞了半个小时，然后被厂长发现...瞎几把连测试都不会...

//        asd an;

//        an.a[0][0]=1;an.a[0][1]=0;an.a[0][2]=0;

//        an.a[1][0]=1;an.a[1][1]=2;an.a[1][2]=1;

//        an.a[2][0]=0;an.a[2][1]=1;an.a[2][2]=0;

//        an=quickmul(2,an);

//        for(int i=0;i<3;i++)

//        {

//            for(int j=0;j<3;j++)

//                printf("%d ",an.a[i][j]);

//            printf("\n");

//        }

//        printf("%lld\n",liu(2,3));

//        asd z;

//        z.a[0][0]=b;

//        z.a[1][0]=b;

//        z.a[2][0]=0;

        LL pp;

        pp=(ans.a[1][0]*b+ans.a[1][1]*b)%q;       //直接得出 次数

        LL k;

        k=liu(a,pp);                //快速幂得出答案

        printf("%lld\n",k%p);

    }

    return 0;

}

/*

可以这样测案例

100

1 3 3 3 233

2 3 3 3 233

3 3 3 3 233

4 3 3 3 233

5 3 3 3 233

*/