莫比乌斯反演
Description
对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数。
Input
第一行一个整数n,接下来n行每行五个整数,分别表示a、b、c、d、k
Output
共n行,每行一个整数表示满足要求的数对(x,y)的个数
Sample Input
2
2 5 1 5 1
1 5 1 5 2
Sample Output
14
3
Hint
100%的数据满足:1≤n≤50000,1≤a≤b≤50000,1≤c≤d≤50000,1≤k≤50000
Solution
首先, 我们可以根据容斥原理将原问题分解为四个小问题,使得每个小问中范围都是从 1 开始。
我们定义
(f(d) = sum^n_{i=1}sum^m_{j=1}gcd(i,j) == d)
(F(d) = sum^n_{i=1}sum^m_{j=1} d | gcd(i,j) = lfloor{m/d}
floor * lfloor{n/d}
floor)
即(F(d) = sum_{d|k}f(k))
根据莫比乌斯反演可得(f(i) = sum_{i|d}mu(d/i)*F(d))
然后我们就可以枚举d来搞一搞啦。
但是考虑到d可能高达(1e5),这是个(O(n^2))的做法,所以我们还要考虑一些优化。
我们发现, 在枚举d的一段区间内,(lfloor{n/d}
floor)和(lfloor{m/d}
floor)只有一个值,且这些值最多只有(sqrt{n}+sqrt{m})个。所以我们处理一个(mu())的前缀和, 每次算一个连续的区间就行了。这样复杂度就降到了(O(nsqrt{n}))级别。
Code
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 1e5 + 10;
int n;
int v[maxn], mu[maxn];
void pre() {
for(int i = 2; i < maxn; i++) {
if(v[i] <= 0)
for(int j = i; j < maxn; j += i) v[j] = i;
}
mu[1] = 1;
for(int i = 2; i < maxn; i++) {
if(v[i] == v[ i / v[i]]) mu[i] = 0;
else mu[i] = -mu[i / v[i]];
}
for(int i = 2; i < maxn; i++) mu[i] += mu[i-1];
}
inline long long cal(int n, int m) {
if(n > m) swap(n, m);
long long res = 0;
for(int i = 1, j; i <= n; i = j + 1) {
j = min(m / (m / i), n / (n / i));
res += (long long)(mu[j] - mu[i - 1]) * (m / i) * (n / i);
}
return res;
}
int main() {
pre();
int t, a , b, c, d, k;
scanf("%d", &t);
for(int tt = 1; tt <= t; tt++) {
scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
if(k == 0) {
printf("0
"); continue;
}
a--, c--;
a /= k, b /= k, c /= k, d /= k;
long long ans = 0;
ans += cal(a, c) + cal(b, d);
ans -= cal(a, d) + cal(b, c);
printf("%lld
", ans);
}
return 0;
}