Summation Of Floor Values

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

Автор Harshil4442, история, 18 месяцев назад, По-английски

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) ?

Harshil4442
18 месяцев назад
6

Комментарии (5)

Показать архивные | Написать комментарий?

sdqe

18 месяцев назад, # |

← Rev. 2 →

+31

$$$\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);
}

→ Ответить

nor

18 месяцев назад, # ^ |

← Rev. 2 →

+20

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;
}

→ Ответить