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

Summation Of Floor Values
Автор Harshil4442, история, 2 года назад, По-английски

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

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

»
2 года назад, # |
← 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);
}
→ Ответить
  • »
    »
    2 года назад, # ^ |
    ← 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;
}
    → Ответить
»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить