Compute sum of divisor count function for triplets of positive integers

Revision en3, by ace_loves_xq, 2020-11-27 12:17:34

Given parameters $$$a, b, c$$$; $$$max(a,b,c) \le 9000$$$. Your task is to compute $$$\sum\limits_{x = 1}^{a} \sum\limits_{y = 1}^{b} \sum\limits_{z = 1}^{c} d(xyz) $$$ where $$$ d(n)$$$ is the divisor count function : the number of positive divisors of $$$n$$$.

This is the final problem in my recent OI Mocktest, I can only solve it to the first subtask : $$$max(a,b,c) \le 200$$$, by iterating over all triplets $$$(x,y,z)$$$ and adding $$$d(xyz)$$$ to the result variable, to compute $$$d(xyz)$$$, I used applied prime sieve.

Can you suggest the algorithm for the final subtask?

Tags #number_theory, #math

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English ace_loves_xq 2020-11-27 13:16:50 19 Tiny change: '(x*y*z) $ where $ ' -> '(x*y*z) $ by modulo $2^30$ where $ '
en6 English ace_loves_xq 2020-11-27 12:26:53 18 Reverted to en4
en5 English ace_loves_xq 2020-11-27 12:25:56 18
en4 English ace_loves_xq 2020-11-27 12:21:45 48
en3 English ace_loves_xq 2020-11-27 12:17:34 66
en2 English ace_loves_xq 2020-11-27 12:16:05 331 Tiny change: 'z)$, I use applied p' -> 'z)$, I used applied p' (published)
en1 English ace_loves_xq 2020-11-27 12:12:49 236 Initial revision (saved to drafts)