题目描述
https://www.luogu.com.cn/problem/P1829
简要题意：求 $\sum_{i=1}^n\sum_{j=1}^m[i,j]$
$n,m\le 10^7$
Solution
令 $f(n)=n\sum_{d|n}d\mu(d)$，这东西依然可以 $O(n)$ 预处理前缀和
所以我们依然能够做到 $O(n)$ 预处理，$O(\sqrt n)$ 单次查询
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
| #include <iostream>
#include <cstdio>
#define maxn 10000010
#define ll long long
using namespace std;
const int p = 20101009;
int n, m, k;
int pri[maxn], cnt, a[maxn]; bool isp[maxn]; ll f[maxn];
void init_isp(int n) {
for (int i = 2; i <= n; ++i) {
if (!isp[i]) pri[++cnt] = i, a[i] = 1;
for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
isp[i * pri[j]] = 1;
if (i % pri[j] == 0) { a[i * pri[j]] = a[i]; break; }
a[i * pri[j]] = i;
}
} f[1] = 1;
for (int i = 1; i <= cnt; ++i)
for (ll j = pri[i]; j <= n; j *= pri[i]) f[j] = j * (1 - pri[i]) % p;
for (int i = 2; i <= n; ++i)
if (a[i] > 1) f[i] = f[i / a[i]] * f[a[i]] % p;
for (int i = 1; i <= n; ++i) f[i] = (f[i] + f[i - 1]) % p;
}
ll F(ll n) { return n * (n + 1) / 2 % p; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m; init_isp(n);
ll ans = 0; if (n > m) swap(n, m);
for (int l = 1, r; l <= n; l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans = (ans + (f[r] - f[l - 1]) * F(n / l) % p * F(m / l)) % p;
} cout << (ans + p) % p << "\n";
return 0;
}
|