首页 > 题解 > codeforces 235E Number Challenge

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$就好了


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×