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).

2 2 2

20

4 4 4

328

10 10 10

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]$$

证明

$$\sum_{i}^nd(i)=\sum_{i}^n\lfloor \frac{n}{i} \rfloor[gcd(n,i)=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]$$

$$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)$$

$$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}

#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);
}