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