SP26017 GCDMAT - GCD OF MATRIX

$$
\begin {aligned}
f(n) = & \sum_{i = 1} ^ a \sum_{j = 1} ^ b [ gcd(i, j) = n ] \\
= & \sum_{i = 1} ^ {\frac a n} \sum_{j = 1} ^ {\frac b n} \sum_{d | gcd(i, j)} \mu(d) \\
= & \sum_{i = 1} ^ {\frac a n} \sum_{j = 1} ^ {\frac b n} \sum_{d | gcd(i, j)} \mu(d) \\
= & \sum_{d = 1} ^ {min({\frac a n}, {\frac b n})} \mu (d) \left \lfloor \frac a {dn} \right \rfloor \left \lfloor \frac b {dn} \right \rfloor \\
\end {aligned}
$$

容斥原理处理即可。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e4 + 10, mod = 1e9 + 7;
int n, m;
int cnt;
LL p[N], low[N], phi[N], sphi[N];
void init()
{
    phi[1] = 1;
    low[1] = 1;
    for (int i = 1; i < N; i++)
    {
        if (!low[i])
        {
            p[++cnt] = i;
            phi[i] = i - 1;
            low[i] = i;
        }
        for (int j = 1; j <= cnt && i * p[j] < N; j++)
        {
            if (i % p[j] == 0)
            {
                if (low[i] == i)
                    phi[i * p[j]] = phi[i] * p[j];
                else
                    phi[i * p[j]] = phi[i / low[i]] * phi[p[j] * low[i]];
                low[i * p[j]] = low[i] * p[j];
                break;
            }
            phi[i * p[j]] = phi[i] * phi[p[j]];
            low[i * p[j]] = p[j];
        }
    }
    for (int i = 1; i < N; i++)
        sphi[i] = (sphi[i - 1] + phi[i]) % mod;
}
LL f(int a, int b)
{
    LL res = 0;
    for (int l = 1, r; l <= min(a, b); l = r + 1)
    {
        r = min(a / (a / l), b / (b / l));
        res += (sphi[r] - sphi[l - 1]) * (LL)(a / l) * (LL)(b / l);
    }
    return res;
}
int main()
{
    init();
    int T;
    scanf("%d%d%d", &T, &n, &m);
    for (int a, b, c, d; T; T--)
    {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        printf("%lld\n", (f(c, d) - f(a - 1, d) - f(b - 1, c) + f(a - 1, b - 1)) % mod);
    }
    return 0;
}