11526 - H(n)

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11526 - H(n)

For n=2147483647, the output should be 46475828386. Read this thread for ideas on a faster algorithm.
Check input and AC output for thousands of problems on uDebug!

RookiE3
New poster
Posts: 16
Joined: Tue Feb 18, 2014 7:59 pm

Re: 11526 - H(n)

How to avoid time-limit exceed in this problem. All I know is the most obvious procedure will give time-limit exceed error. So where can I learn the faster algorithm from, pleeeeze anyone...

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11526 - H(n)

Read this thread for ideas on a faster algorithm.
Check input and AC output for thousands of problems on uDebug!

RookiE3
New poster
Posts: 16
Joined: Tue Feb 18, 2014 7:59 pm

Re: 11526 - H(n)

Why is this code getting WA?

Code: Select all

#include <stdio.h>
#include <math.h>
int main()
{
int n, T, sqrtn, i, l1, l2, k;
unsigned long long sum, sum2;
scanf("%d", &T);

while(T--)
{
scanf("%d", &n);
if(n < 0)
n = -n;
sum = n;
sqrtn = sqrt(n);
k = 1, l2 = n;
for(i=2; i<=sqrtn; i++)
{
l1 = n/i;
sum += l1;
if(l2 != i)
sum += k * (l2 - l1);
l2 = l1;
k++;
}
while(i <= l2)
{
sum += n / i;
i++;
}

printf("%llu", sum);
if(T)
printf("\n");
}
return 0;
}