11526 - H(n)

[helloneo]

hey helloneo
I am not very clear about ur post
can U pls explain a bit more
what is the output for input 20 pls explain...

The output for 20 is of course..
20 + 10 + 6 + 5 + 4 + 3 + 2 + 2 + 2 + 2 + 1 + 1 + ... + 1

If you calculate until sqrt(n) steps, you may know the result of rest of them..

[Obaida]

Thank you helloneo
This helped me a lot. I was thinking something like that & now it's clear.

[zobayer]

hmmm.. helloneo's idea is similar to mine.

lets say n = 20;
k = 1; sum = 0;
so, 20/1 = 20

k = 2
and 20/2 = 10
so, for all the integer divisions, all i = 11 to 20 will produce n/i = 1; (last denominator)
so, you don't need to calculate for 11 to 20, you have 10x1 + 20/1 = 30; (for k = 1)
sum = 30;

k = 3
again 20/3 = 6
so, for all the integer divisions, all i = 7 to 10 will produce n/i = 2; (last denominator)
so, you don't need to calculate for 7 to 10, you have 4x2 + 20/2 = 18; (for k = 2)
sum = sum + 18 = 48;

k = 4
now, 20/4 = 5
so, for all the integer divisions, all i = 6 to 6 will produce n/i = 3; (last denominator)
so, you don't need to calculate for 6, you have 1x3 + 20/3 = 9; (for k = 3)
sum = sum + 9 = 57

as 4 is largest int within sqrt(20),
so lastly you have 1x4 + 20/4 = 9; (for k = 4)
sum = sum + 9 = 66 (ans);
no need to carry any more,

I think you'll now get it. Straight forward idea, will get in time easily. Try in this way for some larger numbers, may be you will be able to find a pattern.

Thanks

[abid_iut]

zobayer can u pls explain the same thing for input 10??
I don't understand why I am taking k=4 for input 20 but not k=3 for input 10.
hope U will help

[zobayer]

for n = 10; go along the similar way:

lets say n = 10;
k = 1; sum = 0;
so, 10/1 = 10

k = 2
and 10/2 = 5
so, for all the integer divisions, all i = 6 to 10 will produce n/i = 1; (last denominator)
so, you don't need to calculate for 6 to 10, you have 5x1 + 10/1 = 15; (for k = 1)
sum = 15;

k = 3
again 10/3 = 3
so, for all the integer divisions, all i = 4 to 5 will produce n/i = 2; (last denominator)
so, you don't need to calculate for 4 to 5, you have 2x2 + 10/2 = 9; (for k = 2)
sum = sum + 9 = 24;

as k is the largest within sqrt(10);
so last we count for k = 3; for 3, one thing here to note that, 10/3 is also 3, so, in such cases, we have to consider once, cause otherwise it will be counted twice.
so, sum = sum + 3 = 27(ans)

for 10, we have the values (imagine RED is not yet counted, and GREEN is already counted, and BLUE is the current term)
k = 1; (10) + 5 + 3 + 2 + 2 + (1 + 1 + 1 + 1 + 1)
k = 2; 10 + (5) + 3 + (2 + 2) + 1 + 1 + 1 + 1 + 1
k = 3; 10 + 5 + (3) + 2 + 2 + 1 + 1 + 1 + 1 + 1;
so you see, 3 is to be counted once as it has no separate counterpart.
if k==n/k then you need to count once;

hope its now clear.

[Obaida]

I think if you look at this part of my code it will be clear,

Code: Select all

removed

Here n is the input & mid holds the sqrt value

[abid_iut]

Thankxxxxxxxxxxxxxxxxxxxxx aaaaaaaaaaaaaaaaaaaa looooooooooooooooooooooot
Opu
this problem was making me almost PAGOL
now AC thanks

[Obaida]

This made me think for half an hour very coll to have the solution.
By the way good luck.

[zobayer]

@@@Obaida, you have put your full code here, OMG, I fear it's a spoiler, pls remove it as soon as possible.

[Md. Mijanur Rahman]

I have got TLE, please anyone honest help me as I am a beginner.
Here is my code

Code: Select all

#include<stdio.h>
int main()
{

	long long n,res,i;
    int j,num;

    scanf("%d",&num);
	for(j=1;j<=num;j++)
	{
	  scanf("%lld",&n);
      if(n<1)
             n=n*(-1);
      res=0;
      for(i=1;i<=n;i=i+1)
      {
            res = (res + n/i);
      }


	  printf("%lld\n",res);
    }
return 0;
}

[Jan]

Read the previous posts, please.

[alamgir kabir]

Anyone help to find my fault. I am getting WA a lot of time.
my code is given below

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int main()
{
    long long res, n, deno, i, temp, sum, test, sq;

    scanf("%lld", &test);

    while( test -- )
    {
        scanf("%lld", &n);
        if( n == 0 )
        {
            printf("0\n");
            continue;
        }

        sq = sqrt( n );

        res = n;
        sum = n;
        deno = 1;

        for( i = 2; i <= n; i ++ )
        {
            temp = n / i;
            sum += ( res - temp ) * deno;
            sum += temp;
            deno = i;
            res = temp;
            if( n / ( i + 1 ) <= deno ) break;

        }
        if( n > 1 && n < 4 ) sum --;
        printf("%lld\n", sum);
    }
    return 0;
}

thnx
everyone

[MRH]

hi "alamgir kabir"
i see your code .your procedure is not ok for this problem such as......
input :
2
100000
99999999
my Acc code output :
1166750
1857511487
your code faild for this case

[alamgir kabir]

Thanks MRH for ur reply. I have to check the problem again?
Am I not the right way? if not, Can u just hint me the way.

[MRH]

Read the previous posts