莫比乌斯反演做题笔记

[HAOI2011]PROBLEM B

https://ac.nowcoder.com/acm/problem/19983

[HAOI2011]Problem b

题意

$Q$ 组询问，给定 $a,b,c,d,k$ , 求 $a <= x <= b, c <= y <= d$ 并且 $gcd(x,y)$ = $k$ 的数对数量。

( $1 <= a,b,c,d,k,Q <= 5 * 10^4$ )

解题思路

定义 $f(l,r)$ 表示 $1 <= x <= l$ 并且 $1 <= y <= r$ 满足 $gcd(x,y) = k$ 的数对数量。

容斥易得，本题的答案即是： $f(b,d) - f(a - 1, d) - f(b, c - 1) + f(a - 1, c - 1)$

那么现在我们的目标是在 $\sqrt{min(l,r)}$ 的时间内快速求出 $f(l,r)$

考虑对于原式进行化简，原式即： $\displaystyle \sum_{i = 1}^{i = l}\sum_{j = 1}^{j = r}{[gcd(i,j) == k]}$

首先是把原式里面的 $k$ 提出来： $\displaystyle \sum_{i = 1}^{i = l}\sum_{j = 1}^{j = r}{[gcd(i,j) == k]}$ $\implies$ $\displaystyle \sum_{i = 1}^{i = \left\lfloor\dfrac{l}{k}\right\rfloor}\sum_{j = 1}^{j = \left\lfloor\dfrac{r}{k}\right\rfloor}{[gcd(i,j) = 1]}$

下一步则是 $gcd(i,j) = 1$ 转化为 $\displaystyle \sum_{d | gcd(i,j)}{\mu(d)}$ :

$\displaystyle \sum_{i = 1}^{i = \left\lfloor\dfrac{l}{k}\right\rfloor}\sum_{j = 1}^{j = \left\lfloor\dfrac{r}{k}\right\rfloor}{[gcd(i,j) == 1]}$ $\implies$ $\displaystyle \sum_{i = 1}^{i = \left\lfloor\dfrac{l}{k}\right\rfloor}\sum_{j = 1}^{j = \left\lfloor\dfrac{r}{k}\right\rfloor}\sum_{d | gcd(i,j)}{\mu(d)}$

又因为 : $[d | gcd(i,j)]$ 等价于 $[d$ $|$ $i]$ && $[d$ $|$ $j]$

$\displaystyle \sum_{i = 1}^{i = \left\lfloor\dfrac{l}{k}\right\rfloor}\sum_{j = 1}^{j = \left\lfloor\dfrac{r}{k}\right\rfloor}\sum_{d | gcd(i,j)}{\mu(d)}$ $\implies$ $\displaystyle \sum_{d = 1}{\mu(d)} \sum_{i = 1}^{i = \left\lfloor\dfrac{l}{k}\right\rfloor}{[d | i]}\sum_{j = 1}^{j = \left\lfloor\dfrac{r}{k}\right\rfloor}{[d|j]}$

然后我们可以知道， $[1,n]$ 内的所有数中 $d$ 的倍数一共有 $\displaystyle \left\lfloor\dfrac{n}{d}\right\rfloor$ 个。所以式子进一步化简：

$\displaystyle \sum_{d = 1}{\mu(d)} \left\lfloor\dfrac{l}{dk}\right\rfloor\left\lfloor\dfrac{r}{kd}\right\rfloor$

现在就可以整一个整除分块乱搞哩！1

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
    int x = 0, flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

const int MAXN = 1e5 + 500;
int Prime[MAXN], mu[MAXN],tot = 0;
bool book[MAXN];
int T,a,b,c,d,k;

void GetPrime() {
    mu[1] = 1;
    for(int i = 2 ; i <= 6e4 ; i ++) {
        if(!book[i]) Prime[++ tot] = i, mu[i] = -1;
        for(int j = 1 ; j <= tot ; j ++) {
            if(Prime[j] * i > 6e4) break;
            book[Prime[j] * i] = 1;
            if(i % Prime[j] == 0) break;
            mu[i * Prime[j]] = -mu[i];
        }
    }
    for(int i = 1 ; i <= 6e4 ; i ++) mu[i] = mu[i - 1] + mu[i];
    return ;
}

int calc(int a, int b) {
    int Ans = 0;
    int mx=a / k, my = b / k;
    for(int l = 1 ,r ;l <= min (mx, my) ; l = r + 1) {
        r = min(mx / (mx / l), my / (my / l));
        Ans += (mx / l) * (my / l) * (mu[r] - mu[l - 1]);
    }
    return Ans;
}

signed main() {
    GetPrime();
    T = read();
    while(T --) {
        a = read(), b = read(), c = read(), d = read(); k = read();
        printf("%lld\n", calc(b, d) - calc(b, c - 1) - calc(a - 1, d) + calc(a - 1, c - 1));
    }
    return  0;
}

闲人碎语文章被收录于专栏

刊载算法学习笔记以及一些题解