签到题我都不会做,我爬了。
首先检测一些明显非法的情况:
签到题我都不会做,我爬了。
首先检测一些明显非法的情况:
一眼看过去是差分约束板子题,实际上也就是差分约束板子题。
复习长链剖分。
傻逼HDU
原题内存1G,贵题内存128M,真的nb
众所周知,这题不是个人也会。
$$ \text{首先可知}d\left( nm \right) =\sum_{a|n}{\sum_{b|m}{\left[
众所周知,这题是个人就会。
$$ \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)}} $$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
#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> |