ace-in-the-hole's blog

By ace-in-the-hole, history, 2 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!

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ace-in-the-hole (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ace-in-the-hole (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ace-in-the-hole (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ace-in-the-hole (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you forgot the modulo $$$2^{30}$$$ path

»
2 months ago, # |
Rev. 3   Vote: I like it +24 Vote: I do not like it

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)$$$

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can I ask that where is the part $$$\mu(d)$$$ function come from

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 3   Vote: I like it +3 Vote: I do not like it

      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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Uhm, the lemma is also very nice. Does it have a name, and where can I read more about it?

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

It looks like 235E - Number Challenge but with bigger limitations, perhaps you can try some ideas from the editorial of that problem