pmtotheam's blog

Need a help for a question
By pmtotheam, history, 4 years ago, In English

Hi guys. I started practicing CSES problemset but I am stuck in the problem below.

https://cses.fi/problemset/task/1082

How to deal with cases like n>10e6?

No need for a straight up answer just a hint

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

Comments Comments (5)
| Write comment?
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it
$$$\displaystyle\sum_{i=1}^n\sum_{d|i}d=\sum_{d=1}^n\left\lfloor \dfrac nd\right\rfloor d$$$
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    constraint for n is 1<=n<=10e12

    In larger cases like n=10e12 where we loop from 1 to 10e12, TLE would be shown.

    I used the same approach but it is not working for larger cases of n.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      think about how many times you will add x to the answer, when x > 1e6.This value is not too big, so we can bruteforce it.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      In this formula, $$$\left\lfloor\dfrac nd\right\rfloor$$$ will be equal for some consecutive $$$d$$$

      So we can calculate the left endpoint $$$l$$$ and the right endpoint $$$r$$$, then,

      $$$\displaystyle\sum_{d=l}^r\left\lfloor \dfrac nd\right\rfloor d=\sum_{d=1}^n\left\lfloor \dfrac nl\right\rfloor d=\left\lfloor \dfrac nl\right\rfloor \sum_{d=l}^r d=\left\lfloor \dfrac nl\right\rfloor \frac{(l+r)(r-l+1)}2$$$

      How to calculate $$$l$$$ and $$$r$$$?

      You can find some regular patterns. Here is the conclusion: (I'm sorry that I don't know how to prove it)

      $$$1$$$ is a left endpoint and for each left endpoint $$$l$$$, the right endpoint $$$r=\left\lfloor \dfrac n{\left\lfloor \dfrac nl\right\rfloor}\right\rfloor$$$.

      We can do it in $$$O(\sqrt n)$$$ time.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Here is the code:

      for(long long l=1,r;l<=n;l=r+1)
{
  r=n/(n/l);
  ans+=(n/l)*(l+r)*(r-l+1)/2;
}

      I hope this code is correct.

      → Reply