洛谷3327 约数个数和 复习

众所周知，这题不是个人也会。

$$ \text{首先可知}d\left( nm \right) =\sum_{a|n}{\sum_{b|m}{\left[ \mathrm{gcd}\left( a,b \right) =1 \right]}} \\ \sum_{1\le i\le n}{\sum_{1\le j\le m}{\sum_{a|i}{\sum_{b|j}{\left[ \mathrm{gcd}\left( a,b \right) =1 \right]}}}} \\ =\sum_{1\le i\le n}{\sum_{1\le j\le m}{\sum_{a|i}{\sum_{b|j}{\sum_{k|gcd\left( a,b \right)}{\mu \left( k \right)}}}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le i\le n}{\sum_{1\le j\le m}{\sum_{a|i}{\sum_{b|j}{\left[ k|\mathrm{gcd}\left( a,b \right) \right]}}}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le a\le n}{\sum_{1\le b\le m}{\sum_{a|i,i\le n}{\sum_{b|j,j\le m}{\left[ k|gcd\left( a,b \right) \right]}}}}} \\ a\gets ak,b\gets bk \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le ak\le n}{\sum_{1\le bk\le m}{\left[ k|gcd\left( ak,bk \right) \right] \lfloor \frac{n}{ak} \rfloor \lfloor \frac{m}{bk} \rfloor}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le a\le \lfloor \frac{n}{k} \rfloor}{\sum_{1\le b\le \lfloor \frac{m}{k} \rfloor}{\lfloor \frac{n}{ak} \rfloor \lfloor \frac{m}{bk} \rfloor}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le a\le \lfloor \frac{n}{k} \rfloor}{\sum_{1\le b\le \lfloor \frac{m}{k} \rfloor}{\lfloor \frac{\lfloor \frac{n}{k} \rfloor}{a} \rfloor \lfloor \frac{\lfloor \frac{m}{k} \rfloor}{b} \rfloor}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \left( \sum_{1\le a\le \lfloor \frac{n}{k} \rfloor}{\lfloor \frac{\lfloor \frac{n}{k} \rfloor}{a} \rfloor} \right) \left( \sum_{1\le b\le \lfloor \frac{m}{k} \rfloor}{\lfloor \frac{\lfloor \frac{m}{k} \rfloor}{b} \rfloor} \right)} \\ S\left( n \right) =\sum_{1\le i\le n}{\lfloor \frac{n}{i} \rfloor} \\ \text{原式}=\sum_{1\le k\le n}{\mu \left( k \right) S\left( \lfloor \frac{n}{k} \rfloor \right) S\left( \lfloor \frac{m}{k} \rfloor \right)} \\ $$

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using int_t = long long int;

const int_t LARGE = 5e4;

using std::cin;
using std::cout;
using std::endl;

int_t S[LARGE + 1];
bool isPrime[LARGE + 1];
int_t factor[LARGE + 1];
int_t mu[LARGE + 1];
int_t muSum[LARGE + 1];

int_t Sx(int_t n) {
    int_t result = 0;
    int_t i = 1;
    while (i <= n) {
        int_t next = n / (n / i);
        result += (next - i + 1) * (n / i);
        i = next + 1;
    }
    return result;
}

int_t query(int_t n, int_t m) {
    if (n > m)
        std::swap(n, m);
    int_t result = 0;
    int_t i = 1;
    while (i <= n) {
        int_t next = std::min(n / (n / i), m / (m / i));
        result += (muSum[next] - muSum[i - 1]) * S[n / i] * S[m / i];
        i = next + 1;
    }
    return result;
}

int main() {
    for (int_t i = 1; i <= LARGE; i++) {
        S[i] = Sx(i);
    }
    memset(isPrime, 1, sizeof(isPrime));
    for (int_t i = 2; i <= LARGE; i++) {
        if (isPrime[i]) {
            factor[i] = i;
            for (int_t j = i * i; j <= LARGE; j += i) {
                isPrime[j] = false;
                if (!factor[j])
                    factor[j] = i;
            }
        }
    }
    mu[1] = muSum[1] = 1;
    for (int_t i = 2; i <= LARGE; i++) {
        int_t factor = ::factor[i];
        if (i / factor % factor == 0)
            mu[i] = 0;
        else
            mu[i] = mu[i / factor] * -1;
        muSum[i] = muSum[i - 1] + mu[i];
    }
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        auto result = query(n, m);
        printf("%lld\n", result);
    }
    return 0;
}