<题解>[POI2007]ZAP-Queries

洛谷的题目链接

让你求\sum\limits_{i=1}^a\sum\limits_{j=1}^b[\gcd(i, j)=d]
莫比乌斯反演入门第一题,只有一点点套路。

让我们做一些可以免去很多分类讨论的约定:a\le b

  1. 很套路地把d抹去:由于\gcd(i, j)=d意味着i,j都要有d这个因子,我们就可以把i,j写成kd的形式,这样我们枚举k就好了:
    \sum\limits_{i=1}^{\lfloor\frac a d\rfloor}\sum\limits_{j=1}^{\lfloor\frac b d\rfloor}[\gcd(i, j)=1]
  2. 莫比乌斯函数性质:[n=1] = \varepsilon=\mu\times 1 = \sum\limits_{d|n}\mu(d),令n=\gcd(i,j),得到:
    \sum\limits_{i=1}^{\lfloor\frac a d\rfloor}\sum\limits_{j=1}^{\lfloor\frac b d\rfloor}\sum\limits_{x|gcd(i, j)}\mu(x)
  3. 上面的第三个sigma可以写成更简单的形式。很显然由于我们的约定,\lfloor\frac a d\rfloor \le \lfloor\frac b d\rfloor,我们的\gcd(\lfloor\frac a d\rfloor,\lfloor\frac b d\rfloor)\le\lfloor\frac a d\rfloor,接下来枚举x
    \sum\limits_{i=1}^{\lfloor\frac a d\rfloor}\sum\limits_{j=1}^{\lfloor\frac b d\rfloor}\sum\limits_{x=1}^{\lfloor\frac a d\rfloor}\mu(x)\times[x|gcd(i,j)]
  4. 这下第三个sigma和i,j没关系了,套路地移项:
    \sum\limits_{x=1}^{\lfloor\frac a d\rfloor}\mu(x)\sum\limits_{i=1}^{\lfloor\frac a d\rfloor}\sum\limits_{j=1}^{\lfloor\frac b d\rfloor}[x|gcd(i,j)]
  5. 我们知道,要让x|\gcd(i, j),那么i,j都要是x的倍数,于是容易得到:
    \sum\limits_{d=1}^{\lfloor\frac a d\rfloor}\mu(d)\lfloor\dfrac {\frac a d} x\rfloor\lfloor\dfrac {\frac b d} x\rfloor
    也就是:
    \sum\limits_{d=1}^{\lfloor\frac a d\rfloor}\mu(d)\lfloor\dfrac a {dx}\rfloor\lfloor\dfrac b {dx}\rfloor

至此,\mu(x)可以根据定义线性筛出,后面的向下取整可以整除分块\sqrt {\min(a, b)}算出,不会的可以去点这里看看这两个东西。

接下来就是代码了:

#include <cstdio>
#include <algorithm>

using std::min;

const int N = 50000 + 100;

bool not_prime[N];
int primes[N], mu[N];

inline void calc_mu(void)
{//线筛mu
    not_prime[1] = true;
    mu[1] = 1;
    for (int i = 2; i != N; ++i)
    {
        if (!not_prime[i])
        {
            mu[i] = -1;
            primes[++primes[0]] = i;
        }
        for (int j = 1; j <= primes[0] && primes[j] * i < N; ++j)
        {
            not_prime[i * primes[j]] = true;
            if (i % primes[j] == 0)
            {
                mu[i * primes[j]] = 0;
                break;
            }
            mu[i * primes[j]] = -mu[i];
        }
    }
}

int main(void)
{
    calc_mu();
    for (int i = 1; i != N; ++i)
        mu[i] += mu[i - 1];
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, m, d;
        scanf("%d %d %d", &n, &m, &d);
        if (n > m)
            n ^= m ^= n ^= m;
        n /= d, m /= d;
        long long ans = 0;
        for (int l = 1, r; l <= n; l = r + 1)
        {//整除分块
            r = min(n / (n / l), m / (m / l));
            ans += (long long)(mu[r] - mu[l - 1]) * (n / l) * (m / l);
        }
        printf("%lld\n", ans);
    }
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注