BZOJ4659 Lcm

Description

给出A,B,考虑所有满足$l\leq a\leq A,l\leq b\leq B$,且不存在n>1使得$n^2$同时整除a和b的有序数
对(a,b),求其lcm(a,b)之和。答案模$2^{30}$。

Input

第一行一个整数T表示数据组数。接下来T行每行两个整数A,B表示一组数据。
T ≤ 2000,A,B ≤ 4e6

Output

对每组数据输出一行一个整数表示答案模$2^{30}$的值

Sample Input

1
2
3
4
5
6
5
2 2
4 6
3 4
5 1
23333 33333

Sample Output

1
2
3
4
5
7
148
48
15
451085813

Solution

枚举gcd以后反演一下

$$
=\sum_{d=1}^{A} μ(d)^2d \sum_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor} \sum_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor} [gcd(i,j)==1] ij\\
=\sum_{d=1}^{A}\mu(d)^2d\sum_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor} \sum_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor}\sum_{D|(i,j)}\mu(D)ij\\
=\sum_{d=1}^{A}\mu(d)^2d\sum_{D=1}^{\lfloor\frac{A}{d}\rfloor}\mu(D)\sum_{i=1}^{\left\lfloor\frac{A}{dD}\right\rfloor} \sum_{j=1}^{\left\lfloor\frac{B}{dD}\right\rfloor}ij\\
=\sum_{d=1}^{A}\mu(d)^2d\sum_{D=1}^{\lfloor\frac{A}{d}\rfloor}\mu(D)D^2\sum_{i=1}^{\left\lfloor\frac{A}{dD}\right\rfloor}i\sum_{j=1}^{\left\lfloor\frac{B}{dD}\right\rfloor}j\\
=\sum_{d=1}^{A} μ(d)^2d \sum_{D=1}^{\left\lfloor\frac{A}{d}\right\rfloor} μ(D)D^2S(\left\lfloor\frac{A}{dD}\right\rfloor)S(\left\lfloor\frac{B}{dD}\right\rfloor)\\
=\sum_{T=1}^{A}S(\left\lfloor\frac{A}{T}\right\rfloor)S(\left\lfloor\frac{B}{T}\right\rfloor)T\sum_{d|T}\mu(d)\mu^2(\frac{T}{d})d\\
=\sum_{T=1}^{A}S(\left\lfloor\frac{A}{T}\right\rfloor)S(\left\lfloor\frac{B}{T}\right\rfloor)F(T)
$$

后面那个$F$再预处理一下,是可以做到O(n)的,蒟蒻不会就写了O(nlogn)的。

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
#include <bits/stdc++.h>
#define IL inline
using namespace std;
IL int read() {
char ch = getchar(); int u = 0, f = 1;
while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); }
return u * f;
}
int T;
#define rep(i, j, k) for (int i = j; i <= k; ++i)
const int maxn = 4e6 + 10;
const int Limit = 4e6;
const int mod = (1 << 30) - 1;
bool fl[maxn]; int pri[maxn], mu[maxn], f[maxn];
IL void sieve() {
mu[1] = 1;
rep(i, 2, Limit) {
if (!fl[i]) pri[++pri[0]] = i, mu[i] = -1;
for (int j = 1; i * pri[j] <= Limit && j <= pri[0]; ++j) {
int to = i * pri[j];
fl[to] = 1;
if (i % pri[j] == 0) {
mu[to] = 0;
break;
} else mu[to] = -mu[i];
}
}
}
int sum(int x) {
return (x * (x + 1) / 2);
}
int main() {
freopen("lcm.in", "r", stdin);
freopen("lcm.out", "w", stdout);

sieve();
rep(i, 1, Limit)
if (mu[i] != 0) for (int j = i; j <= Limit; j += i) f[j] = f[j] + j * (j / i) * mu[j / i];
rep(i, 2, Limit) f[i] = f[i - 1] + f[i];
T = read();
while (T--) {
int n = read(), m = read();
int ans = 0;
for (int i = 1, j; i <= min(n,m); i = j + 1) {
j = min(n / (n / i), m / (m / i));
ans = ans + sum(n / i) * sum(m / i) * (f[j] - f[i-1]);
}
ans = ans & mod;
printf("%d\n",ans);
}
return 0;
}