### ace-in-the-hole's blog

By ace-in-the-hole, history, 5 months ago,

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!

• +11

 » 5 months ago, # |   0 Auto comment: topic has been updated by ace-in-the-hole (previous revision, new revision, compare).
 » 5 months ago, # |   0 Auto comment: topic has been updated by ace-in-the-hole (previous revision, new revision, compare).
 » 5 months ago, # |   0 Auto comment: topic has been updated by ace-in-the-hole (previous revision, new revision, compare).
 » 5 months ago, # |   0 Auto comment: topic has been updated by ace-in-the-hole (previous revision, new revision, compare).
 » 5 months ago, # |   0 I think you forgot the modulo $2^{30}$ path
•  » » 5 months ago, # ^ |   0 Thanks for reminding, I added.
 » 5 months ago, # | ← Rev. 3 →   +24 update: 99710042 implementation of this solution to the problem in the comment belowNot 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)$
•  » » 5 months ago, # ^ |   +13 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?
•  » » » 5 months ago, # ^ |   +3 $i \perp j \rightarrow \gcd(i,j) = 1$
•  » » 5 months ago, # ^ |   +3 Can I ask that where is the part $\mu(d)$ function come from
•  » » » 5 months ago, # ^ | ← Rev. 3 →   +3 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.
•  » » 5 months ago, # ^ |   +10 Uhm, the lemma is also very nice. Does it have a name, and where can I read more about it?
•  » » » 5 months ago, # ^ |   +13 I think this Mobius blog is useful
 » 5 months ago, # |   +14 It looks like 235E - Задача с Числами but with bigger limitations, perhaps you can try some ideas from the editorial of that problem