Harshil4442's blog

Summation Of Floor Values
By Harshil4442, history, 2 years ago, In English

Is there any solution for :

i=1 to n ∑ ⌊C/i⌋ = ?

where, Constraints of C and n are : 1 ≤ C,n ≤ 10^9.

I found solution for,

i=1 to n ∑ ⌊C/i⌋ = 2 * ( i=1 to k ∑ ⌊C/i⌋ ) − k^2

where k = ⌊√n⌋ and this solution is correct only for C=n.

Is there any solution exist for C<n in complexity O(sqrt(n)) or O(log(n)) or O(1) ?

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

Comments Comments (5)
| Write comment?
»
2 years ago, # |
← Rev. 2   Vote: I like it +31 Vote: I do not like it

$$$\lfloor \frac{C}{i} \rfloor$$$ at most $$$2\times \sqrt{C}$$$ different values.
Prove
$$$i \le \sqrt{C} $$$, $$$\lfloor \frac{C}{i} \rfloor$$$ at most $$$\sqrt{C}$$$ different values.
$$$i \ge\sqrt{C} $$$, $$$\lfloor \frac{C}{i} \rfloor \le \sqrt{C}$$$. so it also at most $$$\sqrt{C}$$$ different values. 

ll ans = 0;
for(int l=1,r;l<=C;l=r+1){
	r=C/(C/l);
	ans+=1ll*(r-l+1)*(C/l);
}
→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +20 Vote: I do not like it

    This works only for $$$C = n$$$. However, there is a small fix that works (and the complexity remains the same since we just break early):

    std::uint64_t ans = 0;
n = std::min(n, C);
for (std::uint32_t l = 1, r; l <= n, l = r + 1) {
    auto x = C / l;
    r = std::min(n, C / x);
    ans += (r - l + UINT64_C(1)) * x;
}
    → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply