bzoj2301（莫比乌斯反演）

bzoj2301

题意

求区间 [a, b] 和区间 [c, d] 有多少对数 (x, y) 使得 gcd(x, y) = k 。

分析

参考ppt

参考blog

考虑用容斥分成四次查询，

对于每次查询区间 [1, n] [1, m] 有多少对数使得 gcd = k ，等价于 [1, m / k] [1, n / k] 使得 gcd = 1。

考虑函数 F(k) = (n / k) * (m / k) 表示区间 [1, n] [1, m] 使得 gcd(x, y) 为 k 的倍数的个数。

函数 f(k) 表示区间 [1, n] [1, m] 使得 gcd(x, y) 为 k 的个数。

$ F(d) = \sum_{k\mid d}f(k) => f(k) = \sum_{k\mid d}\mu(\frac d k)F(d) $

f(1) 即为答案。

算法还需要优化，考虑 n / k 这个函数，当 k 越大变化越趋于平缓，也就是说一个整数值会对应一个连续的 k 值区间，对于这些相同的值可以预处理 $\mu$ 函数前缀和，对于 n 和 m 存在公共连续区间的部分 F 函数值不变，直接全部加上即可。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;

int not_prime[MAXN];

int prime[MAXN];

int mu[MAXN];

void getMu() {

    mu[1] = 1;

    int cnt = 0;

    for(int i = 2; i < MAXN; i++) {

        if(!not_prime[i]) {

            prime[cnt++] = i;

            mu[i] = -1;

        }

        for(int j = 0; i * prime[j] < MAXN; j++) {

            not_prime[i * prime[j]] = 1;

            if(i % prime[j] == 0) {

                mu[i * prime[j]] = 0;

                break;

            }

            mu[i * prime[j]] = -mu[i];

        }

    }

    for(int i = 1; i < MAXN; i++) mu[i] += mu[i - 1]; // 前缀和

}

ll cal(int m, int n, int k) {

    int last;

    m /= k; n /= k;

    ll s = 0;

    for(int i = 1; i <= min(n, m); i = last + 1) {

        last = min(n / (n / i), m / (m / i));

        s += (ll)(mu[last] - mu[i - 1]) * (m / i) * (n / i);

    }

    return s;

}

int main() {

    getMu();

    int T;

    scanf("%d", &T);

    while(T--) {

        int a, b, c, d, k;

        scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);

        printf("%d\n", cal(b, d, k) - cal(a - 1, d, k) - cal(b, c - 1, k) + cal(a - 1, c - 1, k));

    }

    return 0;

}

巴特西

bzoj2301（莫比乌斯反演）

bzoj2301

题意

分析

code

最新文章

热门文章