【题解】YY 的 GCD 莫比乌斯函数 LUOGU – 2257

题目戳这里

求：

$$\sum _ {i = 1} ^ n \sum _ {j = 1} ^ m [gcd(i, j) \in prime]$$

按套路来，假定 $n < m$，枚举 $gcd$的值：

$$\sum _ {d = 1} ^ n \sum _ {i = 1} ^ n \sum _ {j = 1} ^ m [gcd(i, j) = d] (d \in prime)$$

同除 $d$：

$$\sum _ {d = 1} ^ n \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor} \sum _ {j = 1} ^ {\lfloor \frac m d \rfloor} [gcd(i, j) = 1] (d \in prime)$$

看到互质就套路：

$$[gcd(i, j) = 1] = \sum _ {t | gcd(i, j)} \mu(t)$$

于是：

$$\sum _ {d = 1} ^ n \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor} \sum _ {j = 1} ^ {\lfloor \frac m d \rfloor} \sum _ {t | gcd(i, j)} \mu(t) (d \in prime)$$

把 $t$放到前面去枚举：

$$\sum _ {d = 1} ^ n \sum _ {t = 1} ^ {\lfloor \frac n d \rfloor} \mu(t) \lfloor \frac n {dt} \rfloor \lfloor \frac m {dt} \rfloor (d \in prime)$$

再套路设 $T = dt$，枚举 $T$和 $d$

$$\sum _ {T = 1} ^ n \lfloor \frac n T \rfloor \lfloor \frac m T \rfloor \sum _ {d | T} \mu(\frac T d)(d \in prime)$$

后面那个 $\sum _ {d | T} \mu(\frac T d)(d \in prime)$$O(n \ln n)$求就行了

前面那个按值分块，每次询问复杂度 $O(\sqrt n)$

#include <bits/stdc++.h>

#define NS (10000001)
#define PS (700000)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int testcase, n, m, p[PS], cnt, mu[NS], g[NS], s[NS];

bool vis[NS];

void preWork()
{
    mu[1] = 1;
    for (int i = 2; i < NS; i += 1)
    {
        if (!vis[i]) p[++cnt] = i, mu[i] = -1;
        for (int j = 1, k; j <= cnt; j += 1)
        {
            k = i * p[j];
            if (k >= NS) break;
            vis[k] = 1, mu[k] = -mu[i];
            if (i % p[j] == 0) { mu[k] = 0; break; }
        }
    }
    for (int i = 1; i <= cnt; i += 1)
        for (int j = p[i]; j < NS; j += p[i])
            s[j] += mu[j / p[i]];
    for (int i = 1; i < NS; i += 1) s[i] += s[i - 1];
}

LL ans;

int main(int argc, char const* argv[])
{
    IN(testcase), preWork();
    while (testcase--)
    {
        IN(n), IN(m), ans = 0;
        if (n > m) swap(n, m);
        for (int i = 1, j; i <= n; i = j + 1)
        {
            j = min(n / (n / i), m / (m / i));
            ans += 1ll * (n / i) * (m / i) * (s[j] - s[i - 1]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}