0.前言
老年退役选手的消遣
1.莫比乌斯函数
(mu)或莫比乌斯函数是指以下函数：
[mu(n) = left{
egin{aligned}
1 quadqquadqquad qquad qquad qquad qquad n = 1
\
quad qquad (-1)^k qquad n = p_1 p_2...p_k, p_i为互不相同的素数
\
0 quadqquadqquadqquad n含有指数大于1的质因子
end{aligned}
ight.
]
莫比乌斯函数的性质：
性质1：对于任意正整数n：
[sum_{dmid n} mu(n) = left{
egin{aligned}
1 qquad n = 1
\
0 qquad n > 1
end{aligned}
ight.
]
性质2：对于任意正整数n：
[sum_{d mid n} frac{mu(d)}{d} = frac{phi(n)}{n}
]
性质2推论：
[sum_{d mid n} dcdot mu(frac{n}{d}) = phi(n)
]
证明： 令(k = frac{n}{d})，带入原式，易得。
线性筛求 (mu)：
lld mu[N];
void euler(lld n) {
lld p[N]; memset(p, 0, sizeof(p));
bool vis[N]; memset(vis, 0, sizeof(vis));
mu[1] = 1; int tot = 0;
for(int i = 2; i <= n; i++) {
if(!vis[i]) {
p[++tot] = i; vis[i] = true;
mu[i] = -1;
}
for(int j = 1; j <= tot && p[j] * i <= n; j++) {
vis[p[j] * i] = true;
if(i % p[j] == 0) mu[i * p[j]] = 0;
else mu[i * p[j]] = mu[i] * (-1);
}
}
}
2.莫比乌斯反演
设(f(n), F(n)) 为定义在正整数集合上的函数。
若 (F(n)) 满足：
[F(n) = sum_{d mid n} f(d)
]
则：
[f(n) = sum_{d mid n} mu(d)F(frac{n}{d})
]
或：
[f(n) = sum_{n mid d} mu(frac{d}{n})F(d)
]
前一个式子证明：（使用定义法）
[右 = sum_{d mid n} mu(d)F(frac{n}{d}) = sum_{d mid n}mu(d)cdot sum_{k mid frac{n}{d}}f(k) = sum_{k mid n} f(k) cdot sum_{d mid frac{n}{k}} mu(d) = f(n) = 左
]
证毕。（第三个等号看不明白可以代个数算算，可以发现两边正好相等）
（也可以使用狄利克雷卷积证明）
3.题目：
求：
[sum_{i = a}^{b} sum_{j = c}^{d}[gcd(i, j) = k]
]
利用二维前缀和将其转化为求
[sum_{i = 1}^{n} sum_{j = 1}^{m}[gcd(i, j) = k]
]
开始推式子：(式子中的除法均为整除）
[
egin{eqnarray*}
&& sum_{i = 1}^{n} sum_{j = 1}^{m}[gcd(i, j) = k] \
&& = sum_{i = 1}^{ frac{n}{k} } sum_{j = 1}^{ frac{m}{k} }[gcd(i, j) = 1]\
&& = sum_{i = 1}^{ frac{n}{k} } sum_{j = 1}^{ frac{m}{k} } sum_{d mid gcd(i, j)} mu(d)
end{eqnarray*}
]
因为 (d mid gcd(i, j)) 可以表示为同时满足 (d mid i, d mid j) ，所以原式
[egin{eqnarray*}
&& = sum_{d = 1}^{min(frac{n}{k}, frac{m}{k})}mu(d) cdot sum_{d mid i}^{frac{n}{k}}sum_{d mid j}^{frac{m}{k}} 1\
&& = sum_{d = 1}^{min(frac{n}{k}, frac{m}{k})}mu(d) frac{n}{kd}frac{m}{kd}
end{eqnarray*}
]
至此，已经可以 (O(n)) 求解了。但题目中询问次数很大，所以需要降低每次询问的复杂度。
考虑整除分块，设当前一段区间的左端点为 (d) ，则右端点为 (min(n/(n / d), m / (m / d))), (mu(d)) 用前缀和实现。
typedef int lld;
const int N = 100005;
lld mu[N];
void euler(lld n) {
lld p[N]; memset(p, 0, sizeof(p));
bool vis[N]; memset(vis, 0, sizeof(vis));
mu[1] = 1; int tot = 0;
for(int i = 2; i <= n; i++) {
if(!vis[i]) {
p[++tot] = i; vis[i] = true;
mu[i] = -1;
}
for(int j = 1; j <= tot && p[j] * i <= n; j++) {
vis[p[j] * i] = true;
if(i % p[j] == 0) mu[i * p[j]] = 0;
else mu[i * p[j]] = mu[i] * (-1);
}
}
for(int i = 1; i <= n; i++) {
mu[i] += mu[i - 1];
}
}
lld a[N], b[N], c[N], d[N], k[N];
lld t, f[N];
lld calc(lld n, lld m, lld k) {
lld p = min(n / k, m / k), tmp = 0;
for(lld i = 1; i <= p; ) {
lld j = min(n / (n / i), m / (m / i));
if(j > p) break;
tmp = tmp + (mu[j] - mu[i - 1]) * (n / i / k) * (m / i / k);
i = j + 1;
}
return tmp;
}
int main() {
// freopen("data.in", "r", stdin);
int n; scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d%d%d%d%d", &a[i], &b[i], &c[i], &d[i], &k[i]);
t = max(t, max(b[i], d[i]));
}
euler(t);
for(int i = 1; i <= n; i++) {
printf("%d
", calc(b[i], d[i], k[i]) - calc(b[i], c[i] - 1, k[i]) - calc(a[i] - 1, d[i], k[i]) + calc(a[i] - 1, c[i] - 1, k[i]));
}
return 0;
}
此题开long long会暴毙。