ace-in-the-hole's blog

By ace-in-the-hole, history, 18 months ago, In English

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(x*y*z) $$$ by modulo $$$2^{30}$$$ 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(x*y*z)$$$ to the result variable, to compute $$$d(x*y*z)$$$, I used applied prime sieve.

Can you suggest the algorithm for the final subtask?

Any help would be highly appreciated!

Read more »

  • Vote: I like it
  • +11
  • Vote: I do not like it