【BZOJ1951】古代猪文（CRT，卢卡斯定理）

题面

题解

要求什么很显然吧。。。

\[Ans=G^{\sum_{k|N}{C_N^k}}\]

给定的模数是一个质数，要求解的东西相当于是上面那坨东西的结果对于\(\varphi\)的取值。

但是\(\varphi\)不是质数，不好直接\(Lucas\)定理，把\(\varphi\)分解质因数之后，

直接\(CRT\)合并结果就好了，所以这个就是\(ex\_Lucas\)

#include
    
     #include
     
      using namespace std;#define ll long long#define RG register#define MAX 50000#define MOD (999911659)#define phi (999911658)inline int read(){    RG int x=0,t=1;RG char ch=getchar();    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();    if(ch=='-')t=-1,ch=getchar();    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();    return x*t;}int fpow(int a,int b,int P){    int s=1;if(!a)return 0;    while(b){if(b&1)s=1ll*s*a%P;a=1ll*a*a%P;b>>=1;}    return s;}int pri[5]={0,2,3,4679,35617},tot=4;int jc[5][MAX],jv[5][MAX],N,G,ans;void pre(int P){    jc[P][0]=1;    for(int i=1;i<=pri[P];++i)jc[P][i]=1ll*jc[P][i-1]*i%pri[P];    jv[P][pri[P]-1]=fpow(jc[P][pri[P]-1],pri[P]-2,pri[P]);    for(int i=pri[P]-2;~i;--i)jv[P][i]=1ll*jv[P][i+1]*(i+1)%pri[P];}int C(int n,int m,int P){return 1ll*jc[P][n]*jv[P][m]%pri[P]*jv[P][n-m]%pri[P];}int Lucas(int n,int m,int P){    if(m>n)return 0;if(!m)return 1;    if(n