CF235E Number Challenge <莫比乌斯反演>

Posted on Symbols count in article: 1.1k Reading time ≈ 4 mins.

Problem

Number Challenge

Time  Limit  per  test:  3  seconds\mathrm{Time\;Limit\;per\;test:\;3\;seconds}
Memory  Limit  per  test:  512  megabytes\mathrm{Memory\;Limit\;per\;test:\;512\;megabytes}
Input:  standard  input\mathrm{Input:\;standard\;input}
Output:  standard  output\mathrm{Output:\;standard\;output}

Description

Let’s denote d(n)d(n) as the number of divisors of a positive integer nn. You are given three integers aa, bb and cc. Your task is to calculate the following sum:
∑i=1a∑j=1b∑k=1cd(i⋅j⋅k)\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c}d(i·j·k)
Find the sum modulo 1073741824(230)1073741824 (2^{30}).

Input

The first line contains three space-separated integers aa, bb and cc (1≤a,b,c≤2000)(1\le a,b,c\le 2000).

Output

Print a single integer — the required sum modulo 1073741824(230)1073741824 (2^{30}).

Examples

Input 1

1
2 2 2

Output 1

1
20

Input 2

1
4 4 4

Output 2

1
328

Input 3

1
10 10 10

Output 3

1
11536

Note

For the first example.
d(1⋅1⋅1)=d(1)=1;d(1·1·1)=d(1)=1;
d(1⋅1⋅2)=d(2)=2;d(1·1·2)=d(2)=2;
d(1⋅2⋅1)=d(2)=2;d(1·2·1)=d(2)=2;
d(1⋅2⋅2)=d(4)=3;d(1·2·2)=d(4)=3;
d(2⋅1⋅1)=d(2)=2;d(2·1·1)=d(2)=2;
d(2⋅1⋅2)=d(4)=3;d(2·1·2)=d(4)=3;
d(2⋅2⋅1)=d(4)=3;d(2·2·1)=d(4)=3;
d(2⋅2⋅2)=d(8)=4.d(2·2·2)=d(8)=4.
So the result is 1+2+2+3+2+3+3+4=201+2+2+3+2+3+3+4=20.

标签：莫比乌斯反演

Translation

给出三个整数a,b,ca,b,c（a,b,c≤2000a,b,c\le2000），求∑i=1a∑j=1b∑k=1cd(ijk)\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c}d(ijk)。

Solution

还记得BZOJ3994【SDOI2015】约束个数和吗？这是那道题的加强版本。

做那道题的时候，我们得到了一个重要结论，即d(x⋅y)=∑i∣x∑j∣y[gcd⁡(i,j)=1]d(x\cdot y)=\sum_{i|x}\sum_{j|y}[\gcd(i,j)=1]。
这个结论可以推广到三维，即

d(x⋅y⋅z)=∑i∣x∑j∣y∑k∣z[gcd⁡(i,j)=1][gcd⁡(j,k)=1][gcd⁡(i,k)=1]d(x\cdot y\cdot z)=\sum_{i|x}\sum_{j|y}\sum_{k|z}[\gcd(i,j)=1][\gcd(j,k)=1][\gcd(i,k)=1]

具体证明见rng_68的证明。

然后就可以很笨拙地套路反演将一个[gcd⁡=1][\gcd=1]化为μ\mu的和式移到前面了。

        ∑p=1a∑q=1b∑r=1cd(pqr)=∑p=1a∑q=1b∑r=1c∑i∣p∑j∣q∑k∣r[gcd⁡(i,j)=1][gcd⁡(i,k)=1][gcd⁡(j,k)=1]=∑i=1a∑j=1b∑k=1c[gcd⁡(i,j)=1][gcd⁡(i,k)=1][gcd⁡(j,k)=1]⌊ai⌋⌊bj⌋⌊ck⌋=∑i=1a∑j=1b∑k=1c∑d∣i,jμ(d)[gcd⁡(i,k)=1][gcd⁡(j,k)=1]⌊ai⌋⌊bj⌋⌊ck⌋=∑k=1c⌊ck⌋∑i=1a∑j=1b∑d∣i,jμ(d)[gcd⁡(i,k)=1][gcd⁡(j,k)=1]⌊ai⌋⌊bj⌋=∑k=1c⌊ck⌋∑d=1min⁡(a,b)μ(d)∑x=1⌊ad⌋∑y=1⌊bd⌋[gcd⁡(x⋅d,k)=1][gcd⁡(y⋅d,k)=1]⌊ax⋅d⌋⌊by⋅d⌋=∑k=1c⌊ck⌋∑d=1min⁡(a,b)μ(d)∑x=1⌊ad⌋⌊ax⋅d⌋[gcd⁡(x⋅d,k)=1]∑y=1⌊bd⌋⌊by⋅d⌋[gcd⁡(y⋅d,k)=1]=∑k=1c⌊ck⌋∑d=1min⁡(a,b)[gcd⁡(d,k)=1]μ(d)∑x=1⌊ad⌋⌊ax⋅d⌋[gcd⁡(x,k)=1]∑y=1⌊bd⌋⌊by⋅d⌋[gcd⁡(y,k)=1]\begin{aligned} &\;\;\;\;\sum_{p=1}^{a}\sum_{q=1}^{b}\sum_{r=1}^{c}d(pqr)\\ &=\sum_{p=1}^{a}\sum_{q=1}^{b}\sum_{r=1}^{c}\sum_{i|p}\sum_{j|q}\sum_{k|r}[\gcd(i,j)=1][\gcd(i,k)=1][\gcd(j,k)=1]\\ &=\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c}[\gcd(i,j)=1][\gcd(i,k)=1][\gcd(j,k)=1]\lfloor\frac{a}{i}\rfloor\lfloor\frac{b}{j}\rfloor\lfloor\frac{c}{k}\rfloor\\ &=\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c}\sum_{d|i,j}\mu(d)[\gcd(i,k)=1][\gcd(j,k)=1]\lfloor\frac{a}{i}\rfloor\lfloor\frac{b}{j}\rfloor\lfloor\frac{c}{k}\rfloor\\ &=\sum_{k=1}^{c}\lfloor\frac{c}{k}\rfloor\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{d|i,j}\mu(d)[\gcd(i,k)=1][\gcd(j,k)=1]\lfloor\frac{a}{i}\rfloor\lfloor\frac{b}{j}\rfloor\\ &=\sum_{k=1}^{c}\lfloor\frac{c}{k}\rfloor\sum_{d=1}^{\min(a,b)}\mu(d)\sum_{x=1}^{\lfloor\frac{a}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{b}{d}\rfloor}[\gcd(x\cdot d,k)=1][\gcd(y\cdot d,k)=1]\lfloor\frac{a}{x\cdot d}\rfloor\lfloor\frac{b}{y\cdot d}\rfloor\\ &=\sum_{k=1}^{c}\lfloor\frac{c}{k}\rfloor\sum_{d=1}^{\min(a,b)}\mu(d)\sum_{x=1}^{\lfloor\frac{a}{d}\rfloor}\lfloor\frac{a}{x\cdot d}\rfloor[\gcd(x\cdot d,k)=1]\sum_{y=1}^{\lfloor\frac{b}{d}\rfloor}\lfloor\frac{b}{y\cdot d}\rfloor[\gcd(y\cdot d,k)=1]\\ &=\sum_{k=1}^{c}\lfloor\frac{c}{k}\rfloor\sum_{d=1}^{\min(a,b)}[\gcd(d,k)=1]\mu(d)\sum_{x=1}^{\lfloor\frac{a}{d}\rfloor}\lfloor\frac{a}{x\cdot d}\rfloor[\gcd(x,k)=1]\sum_{y=1}^{\lfloor\frac{b}{d}\rfloor}\lfloor\frac{b}{y\cdot d}\rfloor[\gcd(y,k)=1]\\ \end{aligned}

令f(n,x)=∑i=1n[gcd⁡(i,x)=1]⌊ni⌋f(n,x)=\sum_{i=1}^{n}[\gcd(i,x)=1]\lfloor\frac{n}{i}\rfloor，那么

Ans=∑k=1c∑d=1min⁡(a,b)[gcd⁡(d,k)=1]μ(d)f(⌊ad⌋,k)f(⌊bd⌋,k)Ans=\sum_{k=1}^{c}\sum_{d=1}^{\min(a,b)}[\gcd(d,k)=1]\mu(d)f(\lfloor\frac{a}{d}\rfloor,k)f(\lfloor\frac{b}{d}\rfloor,k)

到这里就可以暴力做了。由于当且仅当d,kd,k互质时才会计算ff，所以直接暴力计算是可以过20002000这种比较小的数据的。

据说可以做到a,b,c≤105a,b,c\le10^5，不过我不会。

Code

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
#include <bits/stdc++.h>
#define MAX_N 2000
#define MOD 1073741824
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
bool NotPri[MAX_N+5];
int cnt, pri[MAX_N+5], mu[MAX_N+5];
int cache[MAX_N+5][MAX_N+5];
int gcd(int a, int b) {
    if (cache[a][b]) return cache[a][b];
    return cache[a][b] = (b ? gcd(b, a%b) : a);
}
void init() {
    mu[1] = 1;
    for (int i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[cnt++] = i, mu[i] = -1;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > MAX_N) break;
            NotPri[i*pri[j]] = true;
            if (i%pri[j]) mu[i*pri[j]] = -mu[i];
            else {mu[i*pri[j]] = 0; break;}
        }
    }
}
lnt f(int n, int x) {
    lnt ret = 0;
    for (int i = 1; i <= n; i++)
        if (gcd(i, x) == 1) (ret += n/i) %= MOD;
    return ret;
}
int main() {
    int a, b, c; lnt ans = 0;
    read(a), read(b), read(c), init();
    for (int k = 1; k <= c; k++)
        for (int d = 1; d <= min(a, b); d++) if (gcd(d, k) == 1)
            (ans += 1LL*(c/k)*mu[d]%MOD*f(a/d, k)%MOD*f(b/d, k)%MOD) %= MOD;
    return printf("%lld\n", (ans+MOD)%MOD), 0;
}