codeforces235E

发表于 | 分类于

题意

求

\[\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^cd(ijk)\]

其中，\(d(i)\) 表示 \(i\) 的约数个数。

\(a, b, c\leq 2000\)

Solution

设

\[f(i)=\sum_{j=1}^a\sum_{k=1}^b[j\times k == i]\]

则

\begin{align} &\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^cd(ijk) \\ =&\sum_{i=1}^{ab}f(i)\times \sum_{j=1}^cd(ij) \\ =&\sum_{i=1}^{ab}f(i)\times \sum_{j=1}^c\sum_{u|i}\sum_{v|j}[(u,v)==1] \\ =&\sum_{u=1}^{ab}\sum_{v=1}^c[(u,v)==1]\sum_{u|i}^{ab}\times f(i)\times \lfloor \frac{c}{v}\rfloor \\ =&\sum_{u=1}^{ab}\sum_{d|u}\mu(d)\times \sum_{d|v}\lfloor \frac{c}{v}\rfloor\times \sum_{u|i}^{ab}\times f(i) \\ \end{align}

然后我们发现全部都可以预处理出来！！！

因为这些枚举倍数的部分都是独立的，而且单单枚举倍数是可以做到\(O(n\log n)\)的。

所以时间复杂度就为\(O(ab\log ab)\)了，要卡常！

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i, a, b) for (int i = (a), i##_END_ = (b); i <= i##_END_; i++)
#define DNF(i, a, b) for (int i = (a), i##_END_ = (b); i >= i##_END_; i--)
template <typename Tp> void in(Tp &x) {
    char ch = getchar(); x = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
template <typename Tp> Tp chkmax(Tp &x, Tp y) {return x > y ? x : x=y;}
template <typename Tp> Tp chkmin(Tp &x, Tp y) {return x < y ? x : x=y;}
template <typename Tp> Tp Max(const Tp &x, const Tp &y) {return x > y ? x : y;}
template <typename Tp> Tp Min(const Tp &x, const Tp &y) {return x < y ? x : y;}
const int MAXN = 4000010, MOD = (1 << 30);
int a, b, c;
int prime[MAXN];
bool is_prime[MAXN];
int h[MAXN], f[MAXN], q[MAXN], g[MAXN], ans, miu[MAXN];
void get_prime()
{
    miu[1] = 1;
    FOR(i, 2, a * b) {
        if (!is_prime[i]) {
            prime[++prime[0]] = i;
            miu[i] = -1;
        }
        for (int j = 1; prime[j] * i <= i_END_; j++) {
            is_prime[prime[j] * i] = true;
            if (i % prime[j] == 0) {
                miu[prime[j] * i] = 0;
                break;
            }
            miu[prime[j] * i] = -miu[i];
        }
    }
}
int main()
{
    in(a); in(b); in(c); get_prime();
    FOR(i, 1, c) for (int j = i; j <= c; j += i) h[i] = (h[i] + c / j) % MOD;
    FOR(i, 1, a) FOR(j, 1, b) f[i * j]++;
    FOR(i, 1, a * b) for (int j = i; j <= i_END_; j += i)
        q[i] = (q[i] + f[j]) % MOD;
    FOR(i, 1, a * b) for (int j = i; j <= i_END_; j += i)
        g[j] = (g[j] + 1ll * miu[i] * h[i] % MOD) % MOD;
    FOR(i, 1, a * b) g[i] = 1ll * g[i] * q[i] % MOD;
    FOR(i, 1, a * b) ans = (ans + g[i]) % MOD;
    printf("%d\n", ans);
    return 0;
}