294 - Divisors

[necropower]

man, i solved that problem, i tested it with all the possible numbers, and i got a program of a friend of mine, we have the same results, but MY PROGRAM isnt being accepted, and his prg is being accepted, we dont know why!! i am posting my code here, can u guys help me seeing any problem at it??






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

main()
{
long int max,k, i, q, j, maior , maior_n,fim[900],inicio[900];
float raiz;

maior_n = maior = q = 0;

scanf("%d",&max);

for(k = 0; k < max ; k++)
scanf("%d %d",&inicio[k],&fim[k]);

for(k = 0; k < max ; k++)
{
for(j=inicio[k] ; j < (fim[k] + 1) ; j++)
{
raiz = sqrt(j);
for(i=1 ; i < raiz ; i++)
if ((j % i) == 0)
q = q + 2;
if ((raiz * raiz) == j)
q++;
if (q > maior)
{
maior = q;
maior_n = j;
}
q = 0;
}
printf("Between %d and %d, %d has a maximum of %d divisors.n",inicio[k],fim[k],maior_n,maior);
maior = maior_n = q = 0;
}
}

[Ivan Golubev]

> long int max,k, i, q, j, maior , maior_n,fim[900],inicio[900];

What if N > 900? Test your solution with input like:
901
1 1
2 2
...
901 901

and you'll see that it's wrong.

Cut out these arrays. Just read, compute and output one pair by another.

[necropower]

bro, ok, i will use a dynamic allocation array... however, i dont think that this is the problem... )

thanks for the idea...

[[]]'s Necropower

ps:did u see any other problem?



<font size=-1>[ This Message was edited by: necropower on 2002-01-24 11:43 ]</font>

[necropower]

can i do it to every problem? read a input and already put the output??
because i remmember a program[the 3n+1,100] that i had to read ALL the inputs first AND after read them all, put all the outputs.

like, i couldnt read on number then output the answer, then read another number then output the answer... u know?

[[]]'s Necropower

[Ivan Golubev]

>bro, ok, i will use a dynamic allocation array... however, i dont think that this is the problem... )

Insert assert(max <= 900) after scanf(). If you'll get SIGABRT than that's a problem.

>ps:did u see any other problem?

Other code looks OK except this:
if ((raiz * raiz) == j)
strict comparation of the float and integer may not work sometimes. Also your solution a bit slow.

>can i do it to every problem? read a input and already put the output??

Of course you can (in fact, you need to).

>because i remmember a program[the 3n+1,100] that i had to read ALL the inputs first AND after read them all, put all the outputs.

Why do so? Nobody will steal your input file while you computing answer

[necropower]

this program now should work, but it doenst... any idea?

ps: BTW, i am getting WRONG ANSWER not other thing...

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

main()
{
int max,k, i, q, j, maior , maior_n,inicio,fim;

maior_n = maior = q = 0;


scanf("%d",&max);

for(k = 0; k < max ; k++)
{
scanf("%d %d",&inicio,&fim);
for(j=inicio ; j < (fim + 1) ; j++)
{
for(i=1 ; i <= sqrt(j) ; i++)
if ((j % i) == 0)
q++;
if ( ( sqrt(j)* sqrt(j) ) == j)
q = 2*q-1;
else
q = 2*q;
if (q > maior)
{
maior = q;
maior_n = j;
}
q = 0;
}
printf("Between %d and %d, %d has a maximum of %d divisors.n",inicio,fim,maior_n,maior);
maior = maior_n = q = 0;
}
}


<font size=-1>[ This Message was edited by: necropower on 2002-01-25 10:04 ]</font>

[necropower]

i am becoming crazy with this prb.. i dont know where is my error... (

[Ustaad]

Hi..

Just wondered if its problem with printing. Some mailers cut down your print statement to two lines. Try printing in two lines.

Best Regards,
Ustaad

[Revenger]

I tested my program many times, but get WA. Why? Please, help me.

[pascal]
Program p294;

Var N,U,L,t,i,max,j,k : Integer;

Function GetD(NN : Integer) : Integer;
Var i,j,k,l : Integer;
begin
l:=round(sqrt(NN)+1);
k:=0;
for i:=1 to l do
if NN mod i=0 then begin
j:=NN div i;
if j>=i then inc(k);
if j<=i then Break;
inc(k);
end;
GetD:=k;
end;

begin
Read(N);
for t:=1 to N do begin
Read(L,U);
max:=-1;
for i:=L to U do begin
k:=GetD(i);
if k>max then begin
max:=k;
j:=i;
end;
end;
Writeln('Between ',L:0,' and ',U:0,', ',j:0,' has a maximum of ',max:0,' divisors.');
end;
end.[/pascal]

[galois_godel]

the problem is easy?but I can't pass.Can u help me?

program a294(input,output);
var
n,casei,fin,i:integer;
di:integer;
inf,sup:integer;
max,maxdiv,temp:integer;
function getdiv(n,supmax:integer):integer;
var
i:integer;re:integer;
begin
i:=2;re:=1;
while n<>1 do
begin

di:=0;
//if i>trunc(sqrt(n))+1 then begin getdiv:=re*2;exit;end;
if (n mod i)=0 then
begin

di:=1;
n:=n div i;
while (n mod i)=0 do
begin
di:=di+1;
n:=n div i;
end;

end
else
begin
if (i>trunc(exp(ln(n)/3))+1)and(supmax>(re*4)) then begin getdiv:=re*4;exit;end;
end;
re:=re*(di+1);

i:=i+1;
end;

getdiv:=re;
end;

begin
// Insert user code here

readln(n);
for casei:=1 to n do
begin
readln(inf,sup);
max:=1;maxdiv:=inf;
for i:=inf to sup do
begin
temp:=getdiv(i,max);
if temp>max then
begin
max:=temp;
maxdiv:=i;
end;

end;
writeln('Between ',inf,' and ',sup,', ',maxdiv,' has a maximum of ',max,' divisors.');
end;


end.

[pc5971]

I solved the problem 294 and I was accepted but I'm not satisfied because it runs in 1.473 sec. so it's far away from 0.000 or something like this. The idea that I used is that for every number i (from L to H) I calculated the numbers of divisors like this:
[c]
k=0;
t=sqrt(i);
for (l=1;l<=t;l++)
if (!(i%l))
k+=2;
if (t*t==i)
k--;
[/c]

I don't know how can I improve this result... Can I use some Dinamic Programming ? ? ? How ? ? ?

I know that the numbers of divisors for

Code: Select all

  n=p1^e1 * p2^e2 * ... * pm^em 

is

Code: Select all

  (e1+1)*(e2+1)*...*(em+1)

but how can I obtain an dinamic programm using this....

Please help me...

[PMNOX]

Hi
I don't know how to solve this problem in 0.000s
my currect best solution is 0.193 s

hint: use prime numbers

[pc5971]

You mean that you memorize the prime numbers before you calculate the numbers of divisors???

[PMNOX]

yes, I calculate all prime numbers from 2 to sqrt(1000*1000*1000) + 1000, before even reading input data

[deddy one]

*CUT*