Summation Of Floor Values

Revision en2, by Harshil4442, 2022-11-10 08:13:43

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Harshil4442 2022-11-10 08:13:43 21
en1 English Harshil4442 2022-11-10 08:08:06 383 Initial revision (published)