Sum divisor

Một trong những bài toán đơn giản của số học là cho số n. Gọi d(n) là số các ước số của n. Bài toán trên được giải một cách rất đơn giản với những nhận xét rất đơn giản như sau:

• NX1: Nếu n là 1 thì có 1 ước số.
• NX2: Nếu n là 2 thì có 2 ước số.
• NX3: Mọi số n lớn hơn 2 đều có ít nhất hai ước là 1 và n.
• NX4: Nếu a là ước của n thì n/a cũng là ước của n.
• NX5: Số sqrtn = phần nguyên của căn bậc hai của n là ước lớn nhất của n nếu có thể.
• NX6: Nếu n chia hết cho sqrtn thì lúc này theo NX4 có hai ước là sqrtn và sqrrtn/n =sqrtn. Tuy nhiên n chỉ nhận sqrtn là ước một lần.

Dựa và các nhận xét trên bài toán đã được giải. Code sau:

int Count(int n)
{
if(n == 1) return 1;
if(n == 2) return 2;
int res = 2;
int sqrtn = (int)sqrt(n);
for(int i=2; i<= sqrtn; i++)
{
if(n%i==0)
res += 2;
}
if(sqrtn*sqrtn == n) res--;
return res;
}

Thuật toán trên có độ phức tạp O(sqrt(n)). Tuy nhiên thuật toán trên chưa đủ mạnh để giải quyết các bài toán thuộc dạng này. Ví dụ như:
http://codeforces.com/problemset/problem/236/B

B. Easy Number Challenge

time limit per test

2 seconds

memory limit per test

256 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, band c. Your task is to calculate the following sum:

Find the sum modulo 1073741824 (2³⁰).

Input

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

Output

Print a single integer — the required sum modulo 1073741824 (2³⁰).

Sample test(s)

input

2 2 2

output

20

input

5 6 7

output

1520

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.

Để giải bài toán trên chúng ta sử dụng công cụ tìm số ước mạnh hơn nữa. Bài sau tôi sẽ viết về vấn đề này.