当前位置: 首页 > news >正文

(数论大杂烩)古代猪文

HZOJ
洛谷

写在前面

挺久没写过单独的题解了,然后遇到这道做法挺神奇的题,就是那种让人眼前一亮的方法,遂打算写写。

题意

给出两个数\(n, g\),求问

\[g^{\sum_{x|n}~\binom{n}{x}}~mod~P~~(P=999911659) \]

的值。

思路

首先组合数的和一定很大,所以考虑对其取模。组合数在幂次的位置,所以需要考虑用扩展欧拉定理降幂。\(P\) 是个质数,所以$$ g^k ~ mod ~ P = g^{k ~ mod ~ 𝜑(P)}~ mod P$$。然后与\(P\) 互质的数有\(P-1\) 个,所以\(𝜑(P)=P-1\)

但是无法使用卢卡斯定理或扩展卢卡斯定理,我们考虑将模数分解,然后使用中国剩余定理求模数。

\(𝜑(P)\) 可分解为4个较小的质数,我们分别求出组合数模这几个质数的值,再使用CRT,就能解出组合数在模P意义下的数了。然后快速幂即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=999911659,o=999911658,maxn=1e6;
int n,g;
int tot,k[maxn];
int jc[5][maxn],ny[5][maxn],fans[5];
inline int qpow(int x,int y,int p){if(x==0) return 0;int res=1;while(y){if(y&1) res=1ll*res*x%p;x=1ll*x*x%p;y>>=1;}return res;
}
inline int C(int x,int y,int p){if(x<y) return 0;return 1ll*jc[p][x]*ny[p][y]%k[p]*ny[p][x-y]%k[p];
}
inline int lucas(int x,int y,int p){if(!y) return 1;return 1ll*lucas(x/k[p],y/k[p],p)*C(x%k[p],y%k[p],p)%k[p];
}
int main(){cin>>n>>g;if(g==mod) cout<<0,exit(0);int p=o;for(int i=2;i*i<=p;i++)if(p%i==0){k[++tot]=i;while(p%i==0) p/=i;}if(p>1) k[++tot]=p;for(int i=1;i<=tot;i++){jc[i][0]=ny[i][0]=1;for(int j=1;j<k[i];j++) jc[i][j]=1ll*jc[i][j-1]*j%k[i],ny[i][j]=qpow(jc[i][j],k[i]-2,k[i]);}vector<int> ys;for(int i=1;i*i<=n;i++)if(n%i==0){ys.emplace_back(i);if(i*i!=n) ys.emplace_back(n/i);}for(int i=1;i<=tot;i++)for(int j:ys) fans[i]=(fans[i]+lucas(n,j,i))%k[i];int ans=0;for(int i=1;i<=tot;i++){int p=o/k[i];ans=(ans+1ll*fans[i]*p%o*qpow(p,k[i]-2,k[i])%o)%o;}cout<<qpow(g,ans,mod);return 0;
}
http://www.hskmm.com/?act=detail&tid=28115

相关文章:

  • 滥用ACL权限覆盖其他用户S3存储桶中的文件/视频
  • 2025 年最新三维扫描仪厂家权威排行榜:聚焦高精度与多场景适配,为企业与个人用户精选优质品牌推荐高精度/专业/手持激光/工业/便携式三维扫描仪厂家推荐
  • 后端基础-输入/输出件
  • 2025 年净化工程服务商最新权威推荐排行榜:医院净化工程 / 制药厂 / 化工厂 / 实验室 / 无尘车间优选净化工程设计安装施工公司
  • 2025 年最新推荐!国内优质充电桩厂家排行榜,涵盖多场景适配产品,助用户精准选靠谱品牌智能/新能源/电动车/重卡/电动车直流充电桩厂家推荐
  • 实用指南:【图像算法 - 28】基于YOLO与PyQt5的多路智能目标检测系统设计与实现
  • KingView 组态王 6.5下载地址与安装教程
  • 常用接口对比
  • 工具网站网址
  • linux执行脚本命令报错$\r:未找到命令的解决方法
  • 2025 电缆回收推荐榜:广州龙耀 5 星领跑,这些企业适配绿色循环需求
  • 基于最小二乘法的离散数据曲面拟合MATLAB实现方法
  • 20251010——读后感1
  • MOE模型
  • 2025航空插头厂家最新推荐榜:M8 航空插头, m12航空插头, 航空插头公母对接, 航空插头5芯, 航空插头三芯, 航空插头4芯, 航空插头12芯等类型全覆盖,专业定制与可靠品质
  • go使用root用户进行调试
  • 如何反制免费项目管理软件的套路
  • 智能技术与先进制造国际会议(ITAM 2025)
  • 2025智慧工地工程协同项目交付管理软件系统平台公司推荐榜:项目全周期的智能中枢,助力建筑行业数字化转型
  • 1、在pyhcarm中安装包和指定镜像源
  • iOS 26 系统流畅度深度剖析,Liquid Glass 视效与界面滑动的实际测评 - 指南
  • 重庆初阳科技车辆计数厂家:多维度赋能城市建设与工程精细化管理
  • 使用testcenter打出动态流量
  • coze手册
  • css动画已经执行过一次如何再次执行?
  • 缓存监控--来源于网络
  • 20232319 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 2025 年兽药厂家最新推荐榜:级企业技术专利与服务能力全景解析,养殖户选品权威指南
  • 2025 最新隔音板源头厂家口碑推荐榜:阻尼 / 聚酯纤维等全品类适配,资深企业与新锐品牌精选聚酯纤维/墙面/降噪/玻镁/顶部隔音板厂家推荐
  • Google play 内部测试流程