【BZOJ1951】[Sdoi2010]古代猪文 Lucas定理+CRT
定理 CRT
2023-09-11 14:15:24 时间
【BZOJ1951】[Sdoi2010]古代猪文
Description
求$X=\sum\limits_{d|n}C_n^d$,$Ans=G^X (\mod 999911659)$。
Input
有且仅有一行:两个数N、G,用一个空格分开。
Output
有且仅有一行:一个数,表示答案除以999911659的余数。
Sample Input
4 2
Sample Output
2048
HINT
10%的数据中,1 <= N <= 50;
20%的数据中,1 <= N <= 1000;
40%的数据中,1 <= N <= 100000;
100%的数据中,1 <= G <= 1000000000,1 <= N <= 1000000000。
题解:由于n很小,可以暴力枚举约数并用Lucas定理计算$C_n^d$的值。但是最后求的是$G^X%P$,所以X要对P-1取模,然而P-1不是质数,所以先分解质因数然后用CRT合并即可。
注意:G=P时费马小定理不成立。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; typedef long long ll; ll n,m,G,P,ans; ll v[100000],jc[100000],jcc[100000],ine[100000],A[10]; ll lucas(ll a,ll b) { if(a<b) return 0; if(!b) return 1; if(a<P) return jc[a]*jcc[a-b]%P*jcc[b]%P; return lucas(a%P,b%P)*lucas(a/P,b/P)%P; } ll calc() { ll ret=0; jc[0]=jcc[0]=ine[0]=jc[1]=jcc[1]=ine[1]=1; int i; for(i=2;i<P;i++) jc[i]=jc[i-1]*i%P,ine[i]=P-(P/i)*ine[P%i]%P,jcc[i]=jcc[i-1]*ine[i]%P; for(i=1;i<=m;i++) ret=(ret+lucas(n,v[i]))%P; return ret; } inline ll pm(ll x,ll y,ll mod) { ll z=1; while(y) { if(y&1) z=z*x%mod; x=x*x%mod,y>>=1; } return z; } inline ll work(ll a,ll b,ll c) { return (c*pm(a,b-2,b)%b+b)%b; } int main() { scanf("%lld%lld",&n,&G); if(G==999911659) { printf("0"); return 0; } ll i; for(i=1;i*i<n;i++) if(n%i==0) v[++m]=i,v[++m]=n/i; if(i*i==n) v[++m]=i; P=2,A[1]=calc(); P=3,A[2]=calc(); P=4679,A[3]=calc(); P=35617,A[4]=calc(); P=999911658; ans=(ans+P/2*work(P/2,2,A[1]))%P; ans=(ans+P/3*work(P/3,3,A[2]))%P; ans=(ans+P/4679*work(P/4679,4679,A[3]))%P; ans=(ans+P/35617*work(P/35617,35617,A[4]))%P; printf("%lld",pm(G,(ans+P)%P,P+1)); return 0; }
相关文章
- Atitit uke协会产业分类法 艾提拉产业分类法五大类法 目录 1. 配第-克拉克定理概述 产业趋势 有形财物的生产转向无形的服务性生产1 1.1. 农工商趋势法1 1.2. 1940年,英
- Atitit.团队文化建设------影响组织的的一些原理 法则 定理 效应 p826.v4
- 费马小定理
- 神经网络的万能近似定理
- 中心极限定理
- 8.1 握手定理
- 8.3 Dirac定理(1952)
- 8.4 Ore定理(1962)
- 8.8 四色定理
- 8.10 最大流最小割定理
- 8.11 拉姆齐定理(1929)
- 3.5 拉普拉斯定理
- 一文彻底弄明白深度学习中的前馈神经网络(Feed Forward Neural Network)—— 关于万能逼近定理、激活函数、卷积的本质等
- 【数字信号处理】线性时不变系统 LTI “ 输入 “ 与 “ 输出 “ 之间的关系 ( 线性卷积起点定理推导过程 )
- 【数字信号处理】线性时不变系统 LTI “ 输入 “ 与 “ 输出 “ 之间的关系 ( 线性卷积起点定理 | 左边序列概念 | 推理 )
- HDU4869:Turn the pokers(费马小定理+高速幂)
- 同余定理与逆元
- 深度理解软件测试缺陷报告:要点、定理、原则缺一不可
- 均匀分布的熵最大——熵增定理,意味着大家都会趋同,成为乌合之众,最终无差异化。。。在企业管理中这是一件恐怖的事情
- 中值定理的计算
- 概率论大作业3——中心极限定理matlab验证及检验(前置知识)