0%

ECNU3308 lcm 与 gcd (1)

$$\sum_{i=1}^n \sum_{j=1}^m \frac{\mathrm{lcm}(i,j)}{\gcd(i,j)} \bmod 1000000~007$$

其中$1 \leq n, m \leq 10^7$。

前置知识

  • 莫比乌斯反演公式:
    $F(n)=\sum\limits_{d\mid n}f(d)\Rightarrow f(n)=\sum\limits_{d\mid n}\mu(d)F(\frac{n}{d})$
    $F(n)=\sum\limits_{n\mid d}f(d)\Rightarrow f(n)=\sum\limits_{n\mid d}\mu(\frac{d}{n})F(d)$

  • 一些预处理技巧(莫比乌斯函数的预处理等)

  • 一系列的推公式技巧

公式化简


$$a(n,m)=\sum_{i=1}^n \sum_{j=1}^m \frac{\mathrm{lcm}(i,j)}{\gcd(i,j)}$$
$$=\sum\limits_{d=1}^{min(n,m)}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{i\cdot j}{d\cdot d}\cdot [\gcd(i,j)==d]$$
$$=\sum\limits_{d=1}^{min(n,m)}\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}i\cdot j\cdot [\gcd(i,j)==1]$$


$$f(k)=\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}i\cdot j\cdot [\gcd(i,j)==k]$$
以及

$$F(k)=\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}i\cdot j\cdot [\gcd(i,j)为k的倍数]$$

$$=k^2\cdot\sum\limits_{i=1}^{\lfloor\frac{x}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{y}{k}\rfloor}i\cdot j\cdot [\gcd(i,j)为1的倍数]$$

$$=k^2\cdot\frac{(\lfloor\frac{x}{k}\rfloor+1)\cdot \lfloor\frac{x}{k}\rfloor}{2}\cdot \frac{(\lfloor\frac{y}{k}\rfloor+1)\cdot \lfloor\frac{y}{k}\rfloor}{2}$$

$$=k^2\cdot\frac{(\lfloor\frac{x}{k}\rfloor+1)\cdot \lfloor\frac{x}{k}\rfloor\cdot(\lfloor\frac{y}{k}\rfloor+1)\cdot \lfloor\frac{y}{k}\rfloor}{4}$$

那么

$$F(k)=\sum\limits_{k|p}f(p)$$

由莫比乌斯反演公式得

$$f(k)=\sum\limits_{k|p}\mu(\frac{p}{k})F(p)$$

那么原式变成

$$a(n,m)=\sum\limits_{d=1}^{min(n,m)}f(1)$$此时的$x$为$\lfloor\frac{n}{d}\rfloor$,y为$\lfloor\frac{m}{d}\rfloor$。

由上式得

$$f(1)=\sum\limits_{i=1}^{\lfloor\frac{min(n,m)}{d}\rfloor}\mu(i)F(i)$$

$$f(1)=\sum\limits_{i=1}^{\lfloor\frac{min(n,m)}{d}\rfloor}i^2\mu(i)\cdot\frac{(\lfloor\frac{x}{k}\rfloor+1)\cdot \lfloor\frac{x}{k}\rfloor\cdot(\lfloor\frac{y}{k}\rfloor+1)\cdot \lfloor\frac{y}{k}\rfloor}{4}$$

则$$a(n,m)=\sum\limits_{d=1}^{min(n,m)}\sum\limits_{i=1}^{\lfloor\frac{min(n,m)}{d}\rfloor}i^2\mu(i)\cdot\frac{(\lfloor\frac{\lfloor\frac{n}{d}\rfloor}{k}\rfloor+1)\cdot \lfloor\frac{\lfloor\frac{n}{d}\rfloor}{k}\rfloor\cdot(\lfloor\frac{\lfloor\frac{m}{d}\rfloor}{k}\rfloor+1)\cdot \lfloor\frac{\lfloor\frac{m}{d}\rfloor}{k}\rfloor}{4}$$

然后你会发现$f(1)$的取值只与$\lfloor\frac{n}{d}\rfloor$和$\lfloor\frac{m}{d}\rfloor$有关,而这两个的取值只有$O(\sqrt{min(n,m)})$个。
而$f(1)$也可以用同样的方式只需计算$O(\sqrt{\lfloor\frac{min(n,m)}{d}\rfloor})$次。
然后可以预处理前$min(n,m)$个$i^2\mu(i)$的前缀和。
于是复杂度为$O(n+\sqrt{n}\cdot\sqrt{n})=O(n)$。
那么问题就解决了。

小技巧

在处理$(a\cdot b\cdot …)%m$时粗心的小伙伴总会因为太复杂而出错。
这样写基本上就不会出错了。
虽然可能会比较慢,但一般不会卡这个常吧。

1
2
3
4
5
6
7
8
9
10
11
long long mod(long long x, long long p) {
return ((x % p) + p) % p;
}

long long mmod() {
return 1ll;
}
template<typename T, typename ...U>
long long mmod(const T & head, const U &... tail) {
return mod((head % MOD) * mmod(tail...), MOD);
}

最终代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const long long MOD = 1e9 + 7;

long long mod(long long x, long long p = MOD) {
return ((x % p) + p) % p;
}

long long mmod() {
return 1ll;
}

template<typename T, typename ...U>
long long mmod(const T & head, const U &... tail) {
return mod((head % MOD) * mmod(tail...), MOD);
}

const int MAXN = 1e7 + 5;
bool isnpri[MAXN];
vector<int>pri;
ll mu[MAXN];
int n, m;
void init(int r) {
mu[1] = 1;
for(int i = 2; i < r; i++) {
if(!isnpri[i]) {
pri.push_back(i);
mu[i] = -1;
}
for(int j = 0; j < int(pri.size()); j++) {
const int cur = i * pri[j];
if(cur >= r) {
break;
}
isnpri[cur] = true;
if(i % pri[j] == 0) {
mu[cur] = 0;
break;
} else {
mu[cur] = -mu[i];
}
}
}
for(int i = 2; i < r; i++) {
mu[i] = mod(mu[i - 1] + mmod(mu[i], i, i));
}
}

ll calc(int a, int b) {
int r = min(a, b);
ll ret = 0;
for(int i = 1, j; i <= r; i = j + 1) {
j = min(a / (a / i), b / (b / i));
ret = (ret + mmod(mu[j] - mu[i - 1], a / i + 1, a / i, b / i + 1, b / i, 250000002)) % MOD;
}
return ret;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

cin >> n >> m;
ll r = min(n, m), ans = 0;
init(r + 2);
for(int d = 1, e; d <= r; d = e + 1) {
e = min(n / (n / d), m / (m / d));
ans = mod(ans + calc(n / d, m / d) * (e - d + 1));
}
cout << ans << endl;
}

回到开头