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}

×