题目
从\([L, H]\)（\(H-L\leq 10^5\)）选出\(n\)个整数，使得这些数的最大公约数为\(k\)的方案数。
算法
首先有一个很简单的转化，原问题可以简化为：
从\([\lceil {\frac L k} \rceil, \lfloor {\frac H k} \rfloor]\)中选出\(n\)个整数，使得这些数的最大公约数为\(1\)的方案数。
下面，\(L\)的意义不再是原题的意义了，而是\(\lceil {\frac L k} \rceil\)，\(H\)同理。
算法1
设\(dp(i)\)为从选出的这些数最大公约数的为\(i\)的方案数。那么我们可以得到：
\[dp(i)=(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)^n-\sum_{i|j,i < j}dp(j)\]然后我们就这样DP就有\(80\)分了，时间复杂度\(O(H)\)（这里的\(H\)不是指的是题目中的\(H\)，而是重新定义的\(H\)）。
算法2
对上面的DP进行莫比乌斯反演。
设\(F(i)\)为选出的数的最大公约数能够被\(i\)整除的方案数，那么：
\[F(i)=\sum_{i|d}dp(d)\] 反演得：\[dp(d)=\sum_{d|i}\mu(\frac i d) F(i)\] 我们求的是\(dp(1)\)，所以\(d=1\)。\[dp(1)=\sum_{i=1}^H\mu(i) F(i)=\sum_{i=1}^H\mu(i)(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)^n\]这个算起来也是\(O(H)\)的，但是我们还可以继续化简下去。注意到题目中的条件\(H-L\leq 10^5\)。
当\(i \geq H-(L-1)\)，即\(i > H - L\)的时候，我们可以发现一个很神奇的东西，那就是\(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor\)要么等于\(0\)，要么等于\(1\)，所以我们可以把指数去掉！
\[dp(1)=\sum_{i=1}^{H-L}\mu(i)(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)^n+\sum_{i=H-L+1}^H\mu(i)(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)\]
加号左边的式子我们可以暴力算出，现在问题是右边那个怎么算。我们可以计算它的补集：
\[\sum_{i=H-L+1}^H\mu(i)(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)=\sum_{i=1}^H\mu(i)(\lfloor {\frac H i} \rfloor-\lfloor {\frac {L - 1} i}\rfloor)-\sum_{i=1}^{H-L}\mu(i)(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)\]
减号右边的式子我们又可以暴力算出，而左边的，注意到它就是原问题，不过此时\(n=1\)。
原问题：\(\sum_{i=1}^H\mu(i)(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)^n\)
现在我们求的：\(\sum_{i=1}^H\mu(i)(\lfloor {\frac H i} \rfloor-\lfloor {\frac {L - 1} i}\rfloor)\)这样，我们的问题是：从\([L, H]\)中选出\(1\)个整数，使得这些数的最大公约数为\(1\)的方案数。
这个问题的答案就是\(\sum_{i=1}^H\mu(i)(\lfloor {\frac H i} \rfloor-\lfloor {\frac {L - 1} i}\rfloor)\)，若\(L=1\)，那么式子的值就是\(1\)，否则就是\(0\)。
至此，我们就巧妙地解决这道题，时间复杂度\(O(H-L)\)。
代码
#include#include using namespace std;typedef long long i64;const int MAXN = (int) 1e5 + 3;const int MOD = (int) 1e9 + 7;int H, L, n;int myPower(int a, int b) { int ans = 1; while (b) { if (b & 1) ans = (i64) ans * a % MOD; a = (i64) a * a % MOD; b >>= 1; } return ans;}int main() { freopen("number.in", "r", stdin); freopen("number.out", "w", stdout); int k; scanf("%d%d%d%d", &n, &k, &L, &H); L = (L + k - 1) / k; H = H / k; int HL = H - L; static bool notPrime[MAXN]; static int prime[MAXN], cntPrime; static int mu[MAXN]; static int fac[MAXN]; mu[1] = 1; for (int i = 2; i <= HL; i ++) { if (! notPrime[i]) { prime[cntPrime ++] = i; mu[i] = -1; fac[i] = i; } for (int k = 0; k < cntPrime; k ++) { int j = prime[k]; if (j > fac[i]) break; if ((i64) j * i > HL) break; notPrime[j * i] = true; mu[j * i] = fac[i] == j ? 0 : mu[i] * -1; fac[j * i] = j; } } i64 ans = 0; for (int i = 1; i <= HL; i ++) { ans += (i64) mu[i] * myPower(H / i - (L - 1) / i, n); ans %= MOD; } if (L == 1) ans ++; for (int i = 1; i <= HL; i ++) { ans -= mu[i] * (H / i - (L - 1) / i); ans %= MOD; } cout << (ans + MOD) % MOD << endl; return 0;}
算法3
设\(f(i)\)为选出的数的最大公约数为\(i\)且选出的这些数不能全部是同一个数的方案数。
然后我们又可以得到：\[f(i)=(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)^n-(\lfloor {\frac H i} \rfloor - \lfloor {\frac {L - 1} i}\rfloor)-\sum_{i|j,i < j}f(j)\]
可以发现，这里的\(i\)最大只有\(H-L\)，因为对于任意正整数\(x,y(x\neq y)\)，都有\(gcd(x, y)\leq |x-y|\)。然后我们要加上允许全部数选同一个数的方案。