众所周知，这题是个人就会。
$$ \text{钦定}N\le M \\ \sum_{1\le i\le N}{\sum_{1\le j\le M}{\left[ \mathrm{gcd}\left( i,j \right) =p \right]}} \\ \sum_p{\sum_{1\le pi\le N}{\sum_{1\le pj\le M}{\left[ \mathrm{gcd}\left( pi,pj \right) =p \right]}}} \\ \sum_p{\sum_{1\le i\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le j\le \lfloor \frac{M}{p} \rfloor}{\left[ \mathrm{gcd}\left( i,j \right) =1 \right]}}} \\ \sum_p{\sum_{1\le i\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le j\le \lfloor \frac{M}{p} \rfloor}{\sum_{k|gcd\left( i,j \right)}{\mu \left( k \right)}}}} \\ \sum_p{\sum_{1\le k\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le ik\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le jk\le \lfloor \frac{M}{p} \rfloor}{\sum_{k|gcd\left( ik,jk \right)}{\mu \left( k \right)}}}}} \\ \sum_p{\sum_{1\le k\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le i\le \lfloor \frac{N}{kp} \rfloor}{\sum_{1\le j\le \lfloor \frac{M}{kp} \rfloor}{\mu \left( k \right)}}}} \\ \sum_{1\le p\le N,p\,\,is\,\,prime}{\sum_{1\le k\le \lfloor \frac{N}{p} \rfloor}{\mu \left( k \right) \lfloor \frac{N}{kp} \rfloor \lfloor \frac{M}{kp} \rfloor}} \\ T=kp \\ T\le N \\ \sum_{1\le T\le N}{\sum_{p|T\left( T\text{的所有质因数} \right)}{\lfloor \frac{N}{T} \rfloor \lfloor \frac{M}{T} \rfloor \mu \left( \frac{T}{p} \right)}} \\ =\sum_{1\le T\le N}{\lfloor \frac{N}{T} \rfloor \lfloor \frac{M}{T} \rfloor \sum_{p|T,\left( T\text{的所有质因数} \right)}{\mu \left( \frac{T}{p} \right)}} $$
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 2e7;
int f[LARGE + 1];
int fSum[LARGE + 1];
int mu[LARGE + 1];
int factor[LARGE + 1];
bool isPrime[LARGE + 1];
std::vector<int> primes;
int_t query(int_t n, int_t m) {
if (n > m)
std::swap(n, m);
#ifdef DEBUG
cout << "process " << n << " " << m << endl;
#endif
int_t i = 1;
int_t result = 0;
while (i <= n) {
int_t next = std::min(n / (n / i), m / (m / i));
result += (n / i) * (m / i) * (fSum[next] - fSum[i - 1]);
i = next + 1;
}
return result;
}
int main() {
std::ios::sync_with_stdio(false);
memset(isPrime, 1, sizeof(isPrime));
isPrime[1] = false;
for (int_t i = 2; i <= LARGE; i++) {
if (isPrime[i]) {
primes.push_back(i);
for (int_t j = i * i; j <= LARGE; j += i) {
isPrime[j] = false;
if (factor[j] == 0)
factor[j] = i;
}
factor[i] = i;
}
}
mu[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;
}
}
for (auto prime : primes) {
for (int_t j = 1; j * prime <= LARGE; j++) {
f[j * prime] += mu[j];
}
}
#ifdef DEBUG
for (int_t i = 2; i <= 100; i++) {
cout << i << ": factor=" << factor[i] << " isPrime=" << isPrime[i]
<< " mu=" << mu[i] << " f=" << f[i] << endl;
}
#endif
for (int_t i = 2; i <= LARGE; i++)
fSum[i] = fSum[i - 1] + f[i];
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
int_t result = query(n, m);
printf("%lld\n", result);
}
return 0;
}<span id="mce_marker" data-mce-type="bookmark" data-mce-fragment="1"></span>
发表回复