Like the title stated. I really need help with this problem. It's in my training camp for my country's national olympiad.↵
<br>↵
I'll simplify it for you guys.↵
<br>↵
Given three numbers X,Y,Z (X,Y,Z <= 9000),↵
<br>↵
Count all divisors of all number that is a product from three numbers a,b,c such that (a <= X,b <= Y, c <= Z) ↵
and(a divisor and be counted again and again)↵
modulo 2^30↵
<br>↵
To be more clear,a simple algorithm to solve it is:↵
<br>↵
res = 0↵
<br>↵
for i = 1...X↵
<br>for j = 1...Y↵
<br>for k = 1...Z↵
<br>res = res + count_divisors(i*j*k) ↵
<br>count_divisors is a function that counts all positive divisors of an integer↵
<br>It's obviously too slow↵
<br>Find res modulo 2^30↵
<br>Time limit is 2 seconds.↵
<br>It's quite ridiculous guys. Thank you for any help!↵
<br> Example : X = 2,Y = 2, Z = 2↵
<br>↵
the numbers are : 1 , 2 , 2 , 2 , 4 , 4 , 4 , 8↵
<br>↵
total divisors are 20.↵
<br>↵
I'll simplify it for you guys.↵
<br>↵
Given three numbers X,Y,Z (X,Y,Z <= 9000),↵
<br>↵
Count all divisors of all number that is a product from three numbers a,b,c such that (a <= X,b <= Y, c <= Z)
and
modulo 2^30↵
<br>↵
To be more clear,a simple algorithm to solve it is:↵
<br>↵
res = 0↵
<br>↵
for i = 1...X↵
<br>for j = 1...Y↵
<br>for k = 1...Z↵
<br>res = res + count_divisors(i*j*k) ↵
<br>count_divisors is a function that counts all positive divisors of an integer↵
<br>It's obviously too slow↵
<br>Find res modulo 2^30↵
<br>Time limit is 2 seconds.↵
<br>It's quite ridiculous guys. Thank you for any help!↵
<br> Example : X = 2,Y = 2, Z = 2↵
<br>↵
the numbers are : 1 , 2 , 2 , 2 , 4 , 4 , 4 , 8↵
<br>↵
total divisors are 20.↵
