洛谷P3172 [CQOI2015]选数
2022/5/5 23:14:23
本文主要是介绍洛谷P3172 [CQOI2015]选数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
洛谷P3172 [CQOI2015]选数
给定正整数 \(N,K,L,H\)。
在 \([L,H]\) 内选 \(N\) 个整数,易知共有 \((H-L+1)^N\) 种方案。
而我们要求的是 \(N\) 个数的最大公约数为 \(K\) 的方案数。对 \(10^9+7\) 取模。\(1\le N,K\le 10^9,1\le L\le H\le 10^9,H-L\le 10^5\)
令 \(l=\lceil\frac LK\rceil,r=\lfloor\frac HK\rfloor\),显然原问题等价于:
在 \([l,r]\) 内选 \(N\) 个整数,使其最大公约数为 1,求方案数。
记 \(D=r-l\)。
设 \(f_i\) 表示在 \([l,r]\) 内选 \(N\) 个不全相同的整数,使其最大公约数为 \(i\) 的方案数。
Q: 为啥要让 \(N\) 个数不全相同?
A: 这样规定之后,\(\forall i>D\),有 \(f_i=0\),接下来只需考虑 \(f_1\sim f_D\)。
再设 \(F_i\) 表示在 \([l,r]\) 内任选 \(N\) 个不全相同的整数,使 \(i\) 是其公约数的方案数。
记 \([l,r]\) 内 \(i\) 的倍数的个数为 \(S(i)=\lfloor\frac ri\rfloor-\lfloor\frac{l-1}i\rfloor\),易知 \(F_i=S(i)^N-S(i)\)。
接下来可以容斥了:
\[f_i=F_i-f_{2i}-f_{3i}-\cdots \]从 \(i=D\) 开始倒推即可。
最终的答案是 \(f_1+[l=1]\)。(当 \(l=1\) 时,全选 1 也是一种方案)
时间复杂度 \(O(D\log D)\)。
下面再提供一种纯数论做法。
首先,我们有
\[ans=\sum_{d=1}^r\mu(d)S(d)^N \]可以大力推式子得到,不详细写了。
然后我们发现 \(r\) 是 1e9 级别的,线性筛跑不动。
其实杜教筛可以,然而 CQOI2015 时杜教筛尚未普及,因此这是不讲武德的。
注意到 \(d>D\) 时,\(S(d)=0\) 或 \(1\),故 \(S(d)^N=S(d)\)。
\[ans=\sum_{d=1}^D\mu(d)S(d)^N+\sum_{d=D+1}^r\mu(d)S(d) \]把第二个式子差分一下:
\[\sum_{d=D+1}^r\mu(d)S(d)=\sum_{d=1}^r\mu(d)S(d)-\sum_{d=1}^D\mu(d)S(d) \]考虑化简 \(\sum\limits_{d=1}^r\mu(d)S(d)\)。
\(S(d)\) 的定义是 \([l,r]\) 内 \(d\) 的倍数的个数。所以
这样就做完了。还可以再化简整理一下:
\[ans=\sum_{d=1}^D\mu(d)\left(S(d)^N-S(d)\right)+[l=1] \]线性筛 + 整除分块可以做到 \(O(D+\sqrt D\log N)\) 计算。
其实容斥做法也能得出一模一样的式子,只要做一次莫比乌斯反演即可:
\[F_i=\sum_{i|d}f_d\Longleftrightarrow f_i=\sum_{i|d}\mu(d)F_d \]\[\begin{aligned}ans&=f_1+[l=1]\\&=\sum_{d=1}^D\mu(d)F_d+[l=1]\end{aligned} \]这篇关于洛谷P3172 [CQOI2015]选数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升