题目描述

给定正整数G和N，求G^PmodM的值，其中P= sigma(C(N,i) i|N,1<=i<=N),M=999911659

输入格式

第1行：两个数N、G，用一个空格分开。

输出格式

第1行：一个数，表示答案除以999911659的余

样例输入

42

样例输出

2048

数据规模

10%的数据中，1<=N<=50；

20%的数据中，1<=N<=1000；

40%的数据中，1<=N<=100000；

100%的数据中，1<=G<=1000000000，1<=N<=1000000000。

考试考到这个题的时候，本弱一直在纠结怎么骗分。

心情一好，分解了M，发现M是一个质数。

针对40%的数据，可以用费马小定理来骗。（这里不详细描述）

其实这个题的关键就是怎样算组合数，我不知道考的时候抱着怎样的心态，把M-1分解了，发现M-1=2*3*4679*35617（心里惊呼这个M给的好啊）。

利用M-1的分解式，我们可以算出C（N,x）% 2 ，C(N,x) % 3 ，C（N,x）% 4679 ，C(N,x) % 35617（用阶乘式和模逆元）

再用中国剩余定理求解，就求出了某个组合数%（M-1）的答案。

最后一个快速幂就解决。

下面附上我的程序（ms有一种特殊情况会出错）：

#include<iostream>

#include<cstdio>

using namespace std;

typedef long long LLint;

const LLint MAXN=1100000;

const LLint M=999911658LL;

LLint n,g,Cnt,m[20],Ans;

LLint Data[MAXN][4],Jie[MAXN][4],Jie_Ni[MAXN][4];

LLint Get_C(LLint Down,LLint Up,LLint Mod,LLint WDY){

    if(Up==0&&Down==0) return 1;

    if(Up<WDY&&Down<WDY){

        Up=(Up+WDY)%WDY; Down=(Down+WDY)%WDY;

        return Jie[Down][Mod]*Jie_Ni[Up][Mod]%WDY*Jie_Ni[Down-Up][Mod]%WDY;

    }

    //LLint Ret1,Ret2;

    //LLint Up1,Up2,Down1,Down2;

    //Up1=Up%WDY; Down1=Down%WDY;

    //Up2=Up/WDY; Down2=Down/WDY;

    //Ret1=Jie[Down1][Mod]*Jie_Ni[Up1][Mod]%WDY*Jie_Ni[Down1-Up1+1][Mod]%WDY;

    

    //Ret2=Jie[Down2][Mod]*Jie_Ni[Up2][Mod]%WDY*Jie_Ni[Down2-Up2+1][Mod]%WDY;

    //return (Ret2*Ret1%WDY+WDY)%WDY;

    LLint Ret1=Get_C(Down%WDY,Up%WDY,Mod,WDY)%WDY;

    LLint Ret2=Get_C(Down/WDY,Up/WDY,Mod,WDY)%WDY;

    return Ret1*Ret2%WDY;

}

void Ex_Gcd(LLint a,LLint b,LLint &d,LLint &x,LLint &y){

    if(!b){

        d=a; x=1; y=0;

    }

    else{

        Ex_Gcd(b,a%b,d,y,x);

        y-=x*(a/b);

    }

}

LLint China(LLint a,LLint b,LLint c,LLint d){

    LLint Cmd[10],x,y,Ret=0;

    Cmd[1]=a; Cmd[2]=b; Cmd[3]=c; Cmd[4]=d;

    for(LLint i=1;i<=4;i++){

        LLint w=M/m[i];

        Ex_Gcd(m[i],w,d,x,y);

        Ret=(Ret+y*w%M*Cmd[i]%M)%M;

    }

    return (Ret+M)%M;

}

LLint Pow_Mod(LLint a,LLint Times){

    a=a%(M+1);

    LLint Ret=1,s=a;

    while(Times){

        if(Times&1){

            Ret=Ret*s%(M+1LL);

        }

        Times>>=1;

        s=s*s%(M+1LL);

    }

    return Ret;

}

int main()

{

    freopen("cando.in","r",stdin);

    freopen("cando.out","w",stdout);

    scanf("%lld%lld",&n,&g);

    Jie[0][0]=1; Jie_Ni[0][0]=1;

    Jie[0][1]=1; Jie_Ni[0][1]=1;

    Jie[0][2]=1; Jie_Ni[0][2]=1;

    Jie[0][3]=1; Jie_Ni[0][3]=1;

    for(LLint i=1;i<=35618LL;i++){

        Jie[i][0]=Jie[i-1][0]*i%2LL;

        Jie[i][1]=Jie[i-1][1]*i%3LL;

        Jie[i][2]=Jie[i-1][2]*i%4679LL;

        Jie[i][3]=Jie[i-1][3]*i%35617LL;

        LLint x,d,y,a,w;

        if(i<2)

        a=2LL; w=Jie[i][0]; Ex_Gcd(w,a,d,x,y); Jie_Ni[i][0]=(x+2LL)%2LL;

        if(i<3)

        a=3LL; w=Jie[i][1]; Ex_Gcd(w,a,d,x,y); Jie_Ni[i][1]=(x+3LL)%3LL;

        if(i<4679)

        a=4679LL; w=Jie[i][2]; Ex_Gcd(w,a,d,x,y); Jie_Ni[i][2]=(x+4679LL)%4679LL;

        if(i<35617)

        a=35617LL; w=Jie[i][3]; Ex_Gcd(w,a,d,x,y); Jie_Ni[i][3]=(x+35617LL)%35617LL;

    }

    for(LLint i=1;i*i<=n;i++){

        if(n%i==0){

            Data[++Cnt][0]=Get_C(n,i,0LL,2LL);

            Data[Cnt][1]=Get_C(n,i,1LL,3LL);

            Data[Cnt][2]=Get_C(n,i,2LL,4679LL);

            Data[Cnt][3]=Get_C(n,i,3LL,35617LL);

            if(n/i!=i){

                Data[++Cnt][0]=Get_C(n,n/i,0LL,2LL);

                Data[Cnt][1]=Get_C(n,n/i,1LL,3LL);

                Data[Cnt][2]=Get_C(n,n/i,2LL,4679LL);

                Data[Cnt][3]=Get_C(n,n/i,3LL,35617LL);

            }

        }

    }

    m[1]=2; m[2]=3; m[3]=4679; m[4]=35617;

    for(LLint i=1;i<=Cnt;i++)

        Ans=(Ans+China(Data[i][0],Data[i][1],Data[i][2],Data[i][3]))%M;

    printf("%lld",Pow_Mod(g,Ans));

return 0;

}