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

eg:N=6

x=1 y1=6

x=2 y2=3

.

.

.

x=6 y6=1

sum=y1+y2+y3…+y6

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.

solution:

```
ans=0,result=0;
for(i=1;i<=floor(n/2);i++)
ans=ans+n/i;
res=ans+ ceil(n/2);
```

@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 …

sum=0;

for(i=1;i*i<=N;i++)

{

if(N%i==0)

{

sum+=i+N/i;

}

}

if(i*i==N) sum-=i;

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

Yes brother.

Keep helping the guys.

how did u get 6 3 2 1 1 1…

its

6*(1+(1/2)+(1/3))+ n/2;

@shivam9753…thank you brother…