题意
求下面表达式的值，
\[\sum_{a_1=l}^r \sum_{a_2 = l}^r \cdots \sum_{a_n = l}^r [ gcd(a_1,a_2,\ldots, a_n) =k]
\]
其中，\(l, r, n, k \leqslant 10^9\)，且$r-l \leqslant 10^5 $
Solution
\[\sum_{a_1=l}^r \sum_{a_2 = l}^r \cdots \sum_{a_n = l}^r [ gcd(a_1,a_2,\ldots, a_n) =k]
\]
\[=\sum_{a_1=\lceil \frac{l}{k} \rceil}^{\lfloor \frac{r}{k} \rfloor} \sum_{a_2=\lceil \frac{l}{k} \rceil}^{\lfloor \frac{r}{k} \rfloor} \cdots \sum_{a_n=\lceil \frac{l}{k} \rceil}^{\lfloor \frac{r}{k} \rfloor} [ gcd(a_1,a_2,\ldots, a_n) = 1]
\]
莫比乌斯反演经典处理手段，
\[\sum_{d=1}^{\lfloor \frac{r}{k} \rfloor} \mu(d) \times (\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil)^n
\]
如果能够熟练的掌握欧拉筛，那么在\(O(n^{\frac{2}{3}})\)时间复杂度可以拿下，但是显然不是出题人的原意，考虑继续化简。
观察后面的\(\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil\)，我们发现当\(d>\lfloor \frac{r}{k} \rfloor - \lceil \frac{l}{k} \rceil\)时，\(0 \leqslant \lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil \leqslant 1\)，发现\((\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil)^n = \lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil\)，则有，
\[=\sum_{d=1}^{\lfloor \frac{r}{k} \rfloor - \lceil \frac{l}{k} \rceil} \mu(d) \times (\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil)^n + \sum_{d=\lfloor \frac{r}{k} \rfloor - \lceil \frac{l}{k} \rceil + 1}^{\lfloor \frac{r}{k} \rfloor} \mu(d) \times (\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil)
\]
考虑利用差分合并计算，
\[=\sum_{d=1}^{\lfloor \frac{r}{k} \rfloor - \lceil \frac{l}{k} \rceil} \mu(d) \times [(\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil)^n - (\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil)]+ \sum_{d= 1}^{\lfloor \frac{r}{k} \rfloor} \mu(d) \times (\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil)
\]
\[=\sum_{d=1}^{\lfloor \frac{r}{k} \rfloor - \lceil \frac{l}{k} \rceil} \mu(d) \times [(\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil)^n - (\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil)]+ \sum_{d= 1}^{\lfloor \frac{r}{k} \rfloor} \sum_{i|d, \lceil \frac{l}{k} \rceil \leqslant i \leqslant \lfloor \frac{r}{k} \rfloor}\mu(d)
\]
改变枚举顺序，则有，
\[=\sum_{d=1}^{\lfloor \frac{r}{k} \rfloor - \lceil \frac{l}{k} \rceil} \mu(d) \times [(\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil)^n - (\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil)]+ \sum_{i = \lceil \frac{l}{k} \rceil}^{\lfloor \frac{r}{k} \rfloor} \sum_{i|d}\mu(d)
\]
\[=\sum_{d=1}^{\lfloor \frac{r}{k} \rfloor - \lceil \frac{l}{k} \rceil} \mu(d) \times [(\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil)^n - (\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil)]+ \sum_{i = \lceil \frac{l}{k} \rceil}^{\lfloor \frac{r}{k} \rfloor} \epsilon(i)
\]
\[=\sum_{d=1}^{\lfloor \frac{r}{k} \rfloor - \lceil \frac{l}{k} \rceil} \mu(d) \times [(\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil)^n - (\lfloor \frac{r}{dk} \rfloor - \lceil \frac{l}{dk} \rceil)]+ \epsilon(\lceil \frac{l}{k} \rceil)
\]
即使不数论分块，这个题也可以\(O(r-l)\)拿下，反而数论分块会出现很多除以\(0\)的情况，还得手动去枚举那一部分无法处理的前缀和后继，虽然数论分块后真的很快。
Code
点击查看代码
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 50;
const int mod = 1e9 + 7;
inline int read() {
register int res = 0, f = 1;
register char c = getchar();
while (c > '9' || c < '0') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
res = (res << 3) + (res << 1) + c - '0';
c = getchar();
}
return res * f;
}
int n, k, l, r;
int add_mod(int a, int b) {
a += b;
if (a > mod) a -= mod;
if (a < 0) a += mod;
return a;
}
int del_mod(int a, int b) {
a -= b;
if (a < 0) a += mod;
if (a >= mod) a -= mod;
return a;
}
int mul_mod(int a, int b) {
a = 1ll * a * b % mod;
return a;
}
int qpow(int a, int b) {
int base = 1;
while (b) {
if (b & 1) base = mul_mod(base, a);
a = mul_mod(a, a);
b >>= 1;
}
return base;
}
int num;
int prime[N];
int v[N], mu[N], sum_mu[N];
void init() {
int MAX = N - 1;
mu[1] = 1;
for (int i = 2; i <= MAX; ++i) {
if (!v[i]) {
v[i] = i;
mu[i] = -1;
prime[++num] = i;
}
for (int j = 1; j <= num; ++j) {
if (prime[j] > v[i] || i * prime[j] > MAX) break;
v[i * prime[j]] = prime[j];
if (i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
}
mu[i * prime[j]] = -mu[i];
}
}
for (int i = 1; i <= MAX; ++i) sum_mu[i] = add_mod(sum_mu[i - 1], mu[i]);
}
int main () {
n = read(), k = read(), l = read(), r = read();
l = (l - 1) / k;
r = r / k;
init();
int ans = 0, D = r - l;
for (int i = 1, j; i <= D; i = j + 1) {
if (l != 0 && l / i != 0) j = min(min(l / (l / i), r / (r / i)), D);
else j = i;
ans = add_mod(ans, mul_mod(del_mod(sum_mu[j], sum_mu[i - 1]), del_mod(qpow(del_mod(r / i, l / i), n), del_mod(r / i, l / i))));
}
printf("%d\n", ans + (l == 0));
return 0;
}
后记
发现莫比乌斯反演确实好玩，但是近期应该不会再写莫比乌斯反演了吧
换换口味叭
应该不会了吧（心虚