2154
$$\sum_{i = 1}^n \sum_{j= 1}^m lcm(i, j)=\sum_{i=1}^n\sum_{j=1}^m \dfrac{i*j}{(i,j)}$$
$$=\sum_{i=1}^n\sum_{j=1}^m \sum_d \dfrac{ij}{d}[(\frac{i}{d}, \frac{j}{d})==1]=\sum_{d}d\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{d}\rfloor}ij[(i,j)==1]$$
$$=\sum_d d\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{d}\rfloor}ij \sum_{p|(i,j)}\mu(p)=\sum_d d\sum_p p^2\mu(p)\sum_{i=1}^{\lfloor \frac{n}{dp}\rfloor}i\sum_{j=1}^{\lfloor \frac{m}{dp}\rfloor}j$$
$$=\sum_dd\sum_pp^2\mu(p)(\dfrac{(\lfloor \frac{n}{dp} \rfloor + 1)\lfloor \frac{n}{dp} \rfloor}{2})(\dfrac{(\lfloor \frac{m}{dp} \rfloor + 1)\lfloor \frac{m}{dp} \rfloor}{2})$$
$$=\sum_T(\dfrac{(\lfloor \frac{n}{T} \rfloor + 1)\lfloor \frac{n}{T} \rfloor}{2})(\dfrac{(\lfloor \frac{m}{T} \rfloor + 1)\lfloor \frac{m}{T} \rfloor}{2})\sum_{p|T}\dfrac{T}{p}p^2\mu(p)$$
$$=\sum_T(\dfrac{(\lfloor \frac{n}{T} \rfloor + 1)\lfloor \frac{n}{T} \rfloor}{2})(\dfrac{(\lfloor \frac{m}{T} \rfloor + 1)\lfloor \frac{m}{T} \rfloor}{2})\sum_{p|T}Tp\mu(p)$$
需要预处理 $\sum_{d|n}nd\mu(d)$,只需要预处理 $f(n)=\sum_{d|n}d\mu(d)$,$f(n)$ 为积性函数,且 $f(p^t) = 1 - p$。
所以这道题可以搞成多组询问的。
复杂度为 $O(n+q\sqrt n)$
#include <bits/stdc++.h> const int MOD = 20101009; const int N = 1e7 + 7; int prime[N], prin; int f[N]; bool vis[N]; void M(int &x) { if (x >= MOD) x -= MOD; if (x < 0) x += MOD; } void init(int N) { f[1] = 1; for (int i = 2; i < N; i++) { if (!vis[i]) { prime[++prin] = i; M(f[i] = 1 - i); } for (int j = 1; j <= prin && i * prime[j] < N; j++) { vis[i * prime[j]] = 1; if (i % prime[j] == 0) { int temp = i; while (temp % prime[j] == 0) temp /= prime[j]; f[i * prime[j]] = 1LL * (1 - prime[j] + MOD) * f[temp] % MOD; break; } f[i * prime[j]] = 1LL * f[i] * f[prime[j]] % MOD; } } for (int i = 1; i < N; i++) M(f[i] = (f[i - 1] + 1LL * f[i] * i % MOD)); } int cal(int n, int m) { int x = 1LL * n * (n + 1) / 2 % MOD; int y = 1LL * m * (m + 1) / 2 % MOD; return 1LL * x * y % MOD; } int solve(int n, int m) { if (n > m) std::swap(n, m); int ans = 0; for (int i = 1, j; i <= n; i = j + 1) { j = std::min(n / (n / i), m / (m / i)); M(ans += 1LL * cal(n / i, m / i) * (f[j] - f[i - 1] + MOD) % MOD); } return ans; } signed main() { int n, m; scanf("%d%d", &n, &m); init(std::min(n, m) + 1); printf("%d\n", solve(n, m)); return 0; }View Code
2693
$$\sum_{i=1}^n\sum_{j=1}^m \text{lcm}(i, j)$$
$$=\sum_{i=1}^n\sum_{j=1}^m \frac{ij}{\text{gcd}(i,j)}$$
$$=\sum_{d}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij[(i,j)=1]$$
$$=\sum_{d}d\sum_{d'}\mu(d')d'^2 s(\lfloor\frac{n}{dd'}\rfloor)s(\lfloor\frac{m}{dd'}\rfloor)$$
$$=\sum_{T} s(\lfloor\frac{n}{T}\rfloor)s(\lfloor\frac{m}{T}\rfloor)\sum_{d|T}\mu(d)d^2\frac{T}{d}$$$$=\sum_{T} s(\lfloor\frac{n}{T}\rfloor)s(\lfloor\frac{m}{T}\rfloor)T\sum_{d|T}\mu(d)d$$
其中 $s(n) = \frac{n\times (n+1)}{2}$,设 $f(n)=\sum_{d|n}d\mu(d)$,$g(n)=nf(n)$,$f(n)$ 是积性函数,可以直接筛,问题解决。
#include <bits/stdc++.h> const int MOD = 100000009; const int N = 1e7 + 7; int prime[N], prin; int f[N]; bool vis[N]; void M(int &x) { if (x >= MOD) x -= MOD; if (x < 0) x += MOD; } void init(int N) { f[1] = 1; for (int i = 2; i < N; i++) { if (!vis[i]) { prime[++prin] = i; M(f[i] = 1 - i + MOD); } for (int j = 1; j <= prin && i * prime[j] < N; j++) { vis[i * prime[j]] = 1; if (i % prime[j] == 0) { int temp = i; while (temp % prime[j] == 0) temp /= prime[j]; f[i * prime[j]] = 1LL * (1 - prime[j] + MOD) * f[temp] % MOD; break; } f[i * prime[j]] = 1LL * f[i] * f[prime[j]] % MOD; } } for (int i = 1; i < N; i++) f[i] = (1LL * f[i - 1] + 1LL * f[i] * i % MOD) % MOD; } int cal(int n, int m) { int x = 1LL * n * (n + 1) / 2 % MOD; int y = 1LL * m * (m + 1) / 2 % MOD; return 1LL * x * y % MOD; } int solve(int n, int m) { if (n > m) std::swap(n, m); int ans = 0; for (int i = 1, j; i <= n; i = j + 1) { j = std::min(n / (n / i), m / (m / i)); (ans += 1LL * cal(n / i, m / i) * (f[j] - f[i - 1] + MOD) % MOD) %= MOD; } return ans; } signed main() { int T; scanf("%d", &T); init(N - 6); while (T--) { int n, m; scanf("%d%d", &n, &m); printf("%d\n", solve(n, m)); } return 0; }View Code