codeforces 235E Number Challenge

Description

Let’s denote d(n) as the number of divisors of a positive integer n. You are given three integers a, b and c. Your task is to calculate the following sum:

$$\sum_{i =1}^a \sum_{j =1}^b \sum_{k =1}^c d(ijk)$$

Find the sum modulo 1073741824 (2^30).

Input

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

Output

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

Examples

input

2 2 2

output

20

input

4 4 4

output

328

input

10 10 10

output

11536

题解

引理

$$\sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} d(x_1 x_2 \cdots x_k) = \sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} \prod_{i=1}^{k} \left \lfloor \frac{y_i}{x_i} \right \rfloor \prod_{i < j } [gcd(x_i, x_j)=1]$$

证明

首先对于$k=1$，就可以简化一下

$$\sum_{i}^nd(i)=\sum_{i}^n\lfloor \frac{n}{i} \rfloor[gcd(n,i)=1]$$

我们对于$n$的因子可以想一下它的贡献。它一共就计算了$n \over x$次。

现在我们对$k>1$进行归纳：

我们需要证明：

$$d_1(y_1, y_2, \cdots, y_k) = \sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} d(x_1 x_2 \cdots x_k) = f_1 (y_1, y_2, \cdots, y_k) = \sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} \prod_{i=1}^{k} \left \lfloor \frac{y_i}{x_i} \right \rfloor \prod_{i < j} [gcd(x_i, x_j)=1]$$

这样通过$y_1$来归纳一下：

当$y_1=1$时，发现是$k-1$维的证明，成立。

然后对于$y_1>1$，设一下

$$d_2(y_1, y_2, \cdots, y_k) = d_1(y_1, y_2, \cdots, y_k) – d_1(y_1-1, y_2, \cdots, y_k)$$

$$f_2(y_1, y_2, \cdots, y_k) = f_1(y_1, y_2, \cdots, y_k) – f_1(y_1-1, y_2, \cdots, y_k)$$

然后再用$y_2$归纳出$d_2=f_2$。一直做下去，直到归纳$d_{k+1}=f_{k+1}$

就需要证明这个

$$d_{k+1}(y_1, y_2, \cdots, y_k) = d(y_1 y_2 \cdots y_k) = f_{k+1}(y_1, y_2, \cdots, y_k) = \sum_{x_1|y_1} \sum_{x_2|y_2} \cdots \sum_{x_k|y_k} \prod_{i < j} [gcd(x_i, x_j)=1]$$

这样话我们就要考虑所有质因子的贡献。就可以得出了。

$$
\large
\begin{aligned}
ans &= \sum_{i = 1}^a \sum_{j = 1}^b \sum_{k = 1}^cd(ijk)\\
&= \sum_{i = 1}^a {a\over i} \sum_{j = 1}^b {b\over j} \sum_{k = 1}^c {c\over k}[(i,j)=1][(i,k)=1][(j,k)=1]\\
&= \sum_{i = 1}^a {a\over i} \sum_{j = 1}^b {b\over j} \sum_{k = 1}^c {c\over k}[(i,j)=1][(i,k)=1]\sum_{d|(j,k)}\mu(d)\\
&= \sum_{i = 1}^a {a\over i} \sum_{d = 1}^{min(b,c)}\mu(d)\sum_{j = 1}^{b\over d}{b\over jd}[(i,jd)=1]\sum_{k = 1}^{c\over d} {c\over kd}[(i,kd)=1]
\end{aligned}
$$

这样分块求一下再预处理下$\mu$就好了

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2000, mod = 1073741824;
bool p[N + 10];
int ans, a, b, c, mu[N + 10], pr[N + 10], gcd[N + 10][N + 10];
void init() {
    mu[1] = 1;
    for (int i = 2; i <= N; ++i) {
        if (!p[i])
            pr[++pr[0]] = i, mu[i] = -1;
        for (int j = 1; j <= pr[0] && i * pr[j] <= N; ++j) {
            p[i * pr[j]] = 1;
            if (i % pr[j] == 0) {
                mu[i * pr[j]] = 0;
                break;
            }
            mu[i * pr[j]] = -mu[i];
        }
    }
    for (int i = 0; i <= N; ++i) gcd[i][0] = gcd[0][i] = i;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            gcd[i][j] = gcd[j][i] = gcd[j][i % j];
}
int work(int n, int d, int i) {
    int ans = 0;
    for (int j = 1; j <= n; ++j)
        if (gcd[i][j * d] == 1)
            ans += n / j;
    return ans;
}
main() {
    init();
    scanf("%d%d%d", &a, &b, &c);
    for (int i = 1, tmp = 0; i <= a; (ans += 1ll * (a / i) * tmp % mod) %= mod, ++i, tmp = 0)
        for (int d = 1; d <= min(b, c); ++d)
            (tmp += (1ll * mu[d] * work(b / d, d, i) * work(c / d, d, i) % mod + mod) % mod ) %= mod;
    printf("%d\n", ans);
}