Блог пользователя pmtotheam

Автор pmtotheam, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
$$$\displaystyle\sum_{i=1}^n\sum_{d|i}d=\sum_{d=1}^n\left\lfloor \dfrac nd\right\rfloor d$$$
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.