P3455 [POI2007]ZAP-Queries

$f(d) = \sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{m} [gcd(i, j) = d]$

$F(d) = \sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{m} [d | gcd(i, j)] = \lfloor \frac n i\rfloor \lfloor \frac m j\rfloor$

$F(d) = \sum \limits_{d | n}^{} f(n)$

由莫比乌斯反演，

$f(d) = \sum \limits_{d | n}^{} \mu (\frac n d)F(n)$

方便计算，改变一下枚举方式，我们枚举 $x = \frac n d$ ，则

$f(d) = \sum \limits_{x = 1}^{min(n,m)} \mu (x)F(xd)$ $\leftarrow$ 可以看出莫比乌斯反演的实质：容斥原理

将 $F$ 代入，

$f(d) = \sum \limits_{x = 1}^{min(n,m)} \mu (x)\lfloor \frac n {xd}\rfloor \lfloor \frac m {xd}\rfloor$

然后用整除分块即可。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long int
#define rep(i,a,b) for(int i = (a); i <= (b); i ++)
#define dwn(i,a,b) for(int i = (a); i >= (b); i --)
using namespace std;
const int maxn = 50000 + 100;

ll mu[maxn];
int cur, p[maxn], isp[maxn];
void shai()
{
    mu[1] = 1;
    rep(i,2, 50000)
    {
        if(!isp[i])
        {
            p[ ++ cur] = i;
            mu[i] = -1LL;
        }
        for(int j = 1; j <= cur && i * p[j] <= 50000; j ++)
        {
            isp[i * p[j]] = 1;
            if(i % p[j] == 0)
            {
                mu[i * p[j]] = 0;
                break;
            }
            else
            {
                mu[i * p[j]] = mu[i] * mu[p[j]];
            }
        }
    }
    rep(i, 2, 50000)
        mu[i] = mu[i - 1] + mu[i];
}
int main()
{
    shai();
    int T;
    cin >> T;
    rep(i, 1, T)
    {
        ll a, b, d;
        cin >> a >> b >> d;
        ll N = min(a, b) / d;
        ll Ans = 0;
        a /= d;
        b /= d;
        for(ll l = 1LL,r;l <= N; l = r + 1)
        {
            r = min(a / (a / l), b / (b / l));
            Ans += (mu[r] - mu[l - 1]) * (a / l) * (b / l);
        }
        cout << Ans << endl;
    }
    return 0;
}