洛谷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\) 的倍数的个数。所以

\[\begin{aligned} \sum_{d=1}^r\mu(d)S(d) &=\sum_{d=1}^r\sum_{i=l}^r[d|i]\mu(d)\\ &=\sum_{i=l}^r\sum_{d\mid i}\mu(d)\\ &=\sum_{i=l}^r[i=1]\\ &=[l=1] \end{aligned}\]

这样就做完了。还可以再化简整理一下：

\[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} \]