294  Divisors
Moderator: Board moderators

 New poster
 Posts: 20
 Joined: Wed Dec 26, 2001 2:00 am
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;
}
}
#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;
}
}

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia

 New poster
 Posts: 20
 Joined: Wed Dec 26, 2001 2:00 am

 New poster
 Posts: 20
 Joined: Wed Dec 26, 2001 2:00 am
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
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

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
>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
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

 New poster
 Posts: 20
 Joined: Wed Dec 26, 2001 2:00 am
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*q1;
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 20020125 10:04 ]</font>
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*q1;
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 20020125 10:04 ]</font>

 New poster
 Posts: 20
 Joined: Wed Dec 26, 2001 2:00 am
294: Please, help me!
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]
[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]

 New poster
 Posts: 17
 Joined: Wed Jul 17, 2002 5:00 pm
294 WR why??
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.
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.
294 Accepted but not as I want...
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
is
but how can I obtain an dinamic programm using this....
Please help me...
[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
Code: Select all
(e1+1)*(e2+1)*...*(em+1)
Please help me...