Alexa66's blog

find the efficient approach
By Alexa66, history, 4 years ago, In English

can anyone solve it without simple for loop? more efficient approach

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

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

First realize the sum is equivalent to n * m — sum(floor(n / i^2) * i^2). This is because a mod b is equal to a — floor(a / b) * b. Now, you just need to iterate over the factors x of n, figure out the range of i where floor(n / i^2) = x, and use the sum of consecutive squares to find the sum of i^2 in that range and multiply that by x. Total complexity O(sqrtn).

I swear I'll learn latex one day lol...

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

    But won't Root N solution time out given that N is upto 1e18.

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

      It's $$$O(N^\frac{1}{3})$$$ if you consider only distinct values of $$$\frac{N}{i^2}$$$. (by a similar argument as to why there are only $$$O(\sqrt{N})$$$ distinct values of $$$\frac{N}{i}$$$.

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

        Hi thanks for the response. I tried analyzing for a while but could not understand why cube root N. Could you please explain or maybe just share a link to some article that explains it.

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

          If $$$i \le 10^6$$$, you can do it violently.

          If $$$i > 10^6$$$, $$$\lfloor \frac{N}{i^2} \rfloor <= 10^6$$$. So there are $$$O(N^{\frac{1}{3}})$$$ distinct values.

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

      Rip I didn't consider that. Ig you'd do the same thing but need something more clever to only consider values of n / i^2, which the user above says is possible, though I'm unaware how to do that.

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

        I came with the following Root N solution.

        Simply keep adding N%(i^2) till i^2 exceeds N at some value i = j. (j is atmost ceil(root(N)))

        For all remaining values from j to M, simply add (M-j+1)*N to the total. As N % ( value larger than N) = N.

        But again this will time out.

        → Reply