luogu P2480 [SDOI2010]古代猪文
发布时间:2020-12-14 03:50:12 所属栏目:大数据 来源:网络整理
导读:M_sea:这道题你分析完后就是一堆板子 废话 理解完题意后,我们要求的东西是 (G^s(s=sum_{d|n} binom{n}{d})) 但是这个指数 (s) 算出来非常大, 我们可以利用 费马小定理 (a^{(p-1)}equiv1(mod p)(gcd(a,p)=1)) 由此我们可以得到 (G^s equiv G^{s
理解完题意后,我们要求的东西是(G^s(s=sum_{d|n} binom{n}{d})) 但是这个指数(s)算出来非常大, 我们可以利用费马小定理 (a^{(p-1)}equiv1(mod p)(gcd(a,p)=1)) 由此我们可以得到(G^s equiv G^{s mod (p-1)}(mod p)) 组合数部分可以使用(Lucas)定理求解 但是,本题的(mod-1)不是一个质数,它可以质因数分解为(2*3*4679*35617)(分别记为(p_1 p_2 p_3 p_4)) 所以,我们可以对这四个质因子分别算一遍(s),记第(i)个质因子算出来的(s)为(s_i) 我们可以知道[sequiv s_1(mod p_1)][sequiv s_2(mod p_2)][sequiv s_3(mod p_3)][sequiv s_4(mod p_4)] 直接上(CRT)(中国剩余腚♂理)即可求出(s)
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define LL long long #define il inline #define re register using namespace std; const LL md=999911659; const int _=1000000+10,N=4000000+10; il LL rd() { re LL x=0,w=1;re char ch; while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();} while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return x*w; } int n,g; LL jc[36010][4],cj[36010][4],cc[4]; LL p[4]={2,3,4679,35617},prm[1010][2],tt; il LL ksm(LL a,LL b,LL mod) { LL an=1; while(b) { if(b&1) an=(an*a)%mod; a=(a*a)%mod; b>>=1; } return an; } il void init() { for(re int j=0;j<4;j++) jc[0][j]=cj[0][j]=1; for(re int i=1;i<=36000;i++) for(re int j=0;j<4;j++) jc[i][j]=(jc[i-1][j]*i)%p[j],cj[i][j]=ksm(jc[i][j],p[j]-2,p[j]); int nn=n,sqt=sqrt(n); for(re int i=2;i<=sqt&&nn;i++) { if(nn%i!=0) continue; prm[++tt][0]=i; while(nn%i==0) nn/=i,++prm[tt][1]; } if(nn>1) ++prm[++tt][0]=nn,prm[tt][1]=1; } il LL C(int nn,int mm,int q) { if(nn<mm) return 0; if(nn<p[q]) return ((jc[nn][q]*cj[mm][q])%p[q]*cj[nn-mm][q])%p[q]; return (C(nn/p[q],mm/p[q],q)*C(nn%p[q],mm%p[q],q))%p[q]; } il void work(int o,int s) //算每个质因子的贡献 { if(o>tt) { for(re int j=0;j<4;j++) cc[j]=(cc[j]+C(n,s,j))%p[j]; return; } for(re int i=0;i<=prm[o][1];i++) { work(o+1,s); s*=prm[o][0]; } } il void exgcd(LL a,LL &x,LL &y) { if(b==0){x=1,y=0;return;} exgcd(b,a%b,y,x); y-=a/b*x; } il LL CRT() { LL a,b,c,a1,b1,a2,b2,x,y; a1=p[0],b1=cc[0]; for(re int j=1;j<4;j++) { a2=p[j],b2=cc[j]; a=a1,b=a2,c=b2-b1; exgcd(a,y); x=((x*c)%b+b)%b; b1=b1+x*a1,a1=a1*a2; } return b1; } int main() { n=rd(),g=rd(); if(g==md) {putchar(48);return 0;} init(); work(1,1); printf("%lldn",ksm(g,CRT(),md)); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |