suppose N is given to us.We need to find the sum of the number of multiples of x where x starts from x=1 to x=N and the multiple(let it be m) varies from x<=m<=N
what is the best method to do it as the number i.e N can be very large i.e it can be in the order of 10^9
it can be solved in linear time(n/2) with certain division operation.
Will it be a problem.?
you just need n/2 iteration.
I dont think direct formula can be derived, because it includes summmation of harmonic series upto n.
@aniruddha_paul but N is order of 10^9…N/2 is not much optimized to do this question…
u can do this in sqrt(N)…just through 1 to sqrt(N)…if i%N==0 than there are two factor of N : i and N/i…you can get all the factor of N in root(N)…only extra condition to look only when i and N/i will become same in that case it will be add twice for correct this u need u check only if number is proper square of any number than subtract that number from sum and u will get desired output…hope it is clear …
you can optimize it to sqrt(n).
As rcsldav2017 said.
actually its the logic of the question:http://www.codechef.com/problems/COOLGUYS
But in the editorial They have used an approach which I m not getting it.
Plz help me out.
How?For carrying the multiplication starting from 1—>N its is O(n)
and N is 10^9.
How are you getting harmonic series over here.??
according to the eg above
6 3 2 1 1 1
is ii a harmonic series???
Keep helping the guys.
how did u get 6 3 2 1 1 1…
@shivam9753…thank you brother…