514977059's blog

Need help in CSES problem
By 514977059, history, 5 years ago, In English

Hi, I'm stuck on this problem, but I'm unable to find a solution which I could understand. Can someone explain it to me

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

Comments Comments (14)
| Write comment?
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

click

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

For a divisor d, d can appear floor(n, d) times as divisor of all number 1-n. E.g. n=100, d=2 then 2 can appear 50 times as divisor

We also know that every divisor from (floor(n, d+1)+1, floor(n, d)) can appear d times. E.g. n=100, d=2 then every divisor from (34, 50) can appear 2 times.

Can you see O(sqrt(n)) approach from this?

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

    thanks, I coded it and it worked, turns out it's not that hard ....

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

We can see that the sum is equivalent to

$$$\sum_{i} \lfloor\dfrac{n}{i}\rfloor * i$$$

It's easy to see that

$$$\lfloor\dfrac{n}{i}\rfloor$$$

has only O(sqrt(N)) distinct values, so we can group together ranges that has the same division value and use A.P sum.

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

    In case you're wondering why the sum has only $$$O(\sqrt{n})$$$ distinct values:

    There are 2 cases for $$$\left \lfloor{\frac{n}{i}}\right \rfloor$$$.

    1. $$$i \leq \sqrt{n}$$$. There are only $$$\sqrt{n}$$$ such values.
    2. $$$i > \sqrt{n}$$$. In this case, $$$\left \lfloor{\frac{n}{i}}\right \rfloor < \sqrt{n}$$$, so there are at most $$$\sqrt{n}$$$ distinct values.

    In total, we have at most $$$2 \cdot \sqrt{n} = O(\sqrt{n})$$$ distinct values.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
"""
Well there is a simple O(n) method to do this problem. It is shown in the
below python code.

n = int(input()); ans = 0;
for i in range(1, n+1):
    ans += i * (n // i);
print(ans);

But we need to solve this problem in O(sqrt N) to pass the test cases.
So this is kinda hack. For the first half of the (sqrt N) values we will use
different technique, and use O(n) solution for the rest remaining half.
"""

M = 10**9+7
## AP Summation Formulae; 
def summation(l, r):
    n = r - l + 1
    return n * ( l + r) // 2;

## First Part;
n = int(input()); ans = 0;
i = 1; minVal = n
while( i*i <= n):
    l = n // (i + 1); r = n // i
    if(l >= r):
        continue
    ans+= i * (summation(l + 1, r))
    minVal = l
    ans %= M;
    i += 1;

## Second Part;
for i in range(1, minVal + 1):
    ans += i * (n // i)
    ans %= M;
 
print(ans % M);
→ Reply