Codeforces 235E. Number Challenge DP

dp(a,b,c,p) = sigma ( dp(a/p^i,b/p^j,c/p^k) * ( 1+i+j+k) )

表示用小于等于p的素數去分解的結果有多少個

E. Number Challenge

time limit per test

 3 seconds

memory limit per test

 512 megabytes

input

 standard input

output

 standard output

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:

Find the sum modulo 1073741824 (230).

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

Sample test(s)

Note

For the first example.

d(1·1·1) = d(1) = 1;

d(1·1·2) = d(2) = 2;

d(1·2·1) = d(2) = 2;

d(1·2·2) = d(4) = 3;

d(2·1·1) = d(2) = 2;

d(2·1·2) = d(4) = 3;

d(2·2·1) = d(4) = 3;

d(2·2·2) = d(8) = 4.

So the result is 1 + 2 + 2 + 3 + 2 + 3 + 3 + 4 = 20.

本文轉自mfrbuaa部落格園部落格，原文連結：http://www.cnblogs.com/mfrbuaa/p/5407021.html，如需轉載請自行聯系原作者