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!
Auto comment: topic has been updated by ace_loves_xq (previous revision, new revision, compare).
Auto comment: topic has been updated by ace_loves_xq (previous revision, new revision, compare).
Auto comment: topic has been updated by ace_loves_xq (previous revision, new revision, compare).
Auto comment: topic has been updated by ace_loves_xq (previous revision, new revision, compare).
I think you forgot the modulo $$$2^{30}$$$ path
Thanks for reminding, I added.
update: 99710042 implementation of this solution to the problem in the comment below
Not sure if it is correct, just some ideas.
Assume that $$$n = \max(a,b,c)$$$
Lemma: $$$d(xyz) = \sum_{i \mid x} \sum_{j \mid y} \sum_{k \mid z} [i \perp j, j \perp k, i \perp k]$$$
Now let's calculate the answer
\sum_{x=1}^a \sum_{y=1}^v \sum_{z=1}^c \sum_{i \mid x} \sum_{j \mid y} \sum_{k \mid z} [i \perp j, j \perp k, i \perp k] = \\
\sum_{i=1}^a \sum_{j=1}^b \sum_{k=1}^c \lfloor \frac{a}{i} \rfloor \lfloor \frac{b}{j} \rfloor \lfloor \frac{c}{k} \rfloor [i \perp j][j \perp k][i \perp k] = \\
\sum_{i=1}^a \lfloor \frac{a}{i} \rfloor \sum_{j=1}^b [i \perp j] \lfloor \frac{b}{j} \rfloor \sum_{k=1}^c [i \perp k] \lfloor \frac{c}{k} \rfloor \sum_{d \mid j, d\mid k} \mu(d)
= \\
\sum_{i=1}^a \lfloor \frac{a}{i} \rfloor \sum_{d=1}^n \mu(d) [d \perp i] (\sum_{p=1}^{\lfloor \frac{b}{d} \rfloor} [p \perp i] \lfloor \frac{b}{dp} \rfloor) (\sum_{q=1}^{\lfloor \frac{c}{d} \rfloor} [q \perp i] \lfloor \frac{c}{dq} \rfloor) \\
$$$
Let $$$W(k,x) = \sum_{i=1}^{k} [i \perp x] \lfloor \frac{k}{i} \rfloor$$$
Answer is
\sum_{i=1}^a \lfloor \frac{a}{i} \rfloor \sum_{d=1}^n \mu(d) [d \perp i] W(\lfloor \frac{b}{d} \rfloor,i) \cdot W(\lfloor \frac{c}{d} \rfloor,i) \\
$$$
Let's fix $$$i$$$. Note that there are only $$$O(\sqrt{n})$$$ possible values of $$$\lfloor \frac{n}{i} \rfloor $$$. Once we calculate the prefix sum of $$$A_j = [j \perp i]$$$ We can caculate $$$W(k,i)$$$ in $$$O(\sqrt{k})$$$.
Also there are no more than $$$O(\sqrt n)$$$ possible values of the pair $$$(\lfloor \frac{b}{d} \rfloor,\lfloor \frac{c}{d} \rfloor ) $$$, we only need to calculate $$$O(\sqrt n)$$$ times of $$$W(k,x)$$$. So the complexity should be $$$O(n^2)$$$
Thanks for the great solution. It is really clear and precise, it just that im quite weak at math , so can you explain what does the perpendicular-like symbol mean?
$$$i \perp j \rightarrow \gcd(i,j) = 1$$$
Can I ask that where is the part $$$\mu(d)$$$ function come from
Here $$$\mu$$$ denotes to the Mobius function. You can google "Mobius inversion" to learn more about it. It appears here because I used the formula $$$[i \perp j] = \sum_{d \mid i, d \mid j} \mu(d)$$$.
P.S. I think OP is familiar with the cp number theory stuffs so I didn't explain everything here. If anyone has further questions you are welcomed to PM me.
Uhm, the lemma is also very nice. Does it have a name, and where can I read more about it?
I think this Mobius blog is useful
It looks like 235E - Number Challenge but with bigger limitations, perhaps you can try some ideas from the editorial of that problem