## 294 - Divisors

Moderator: Board moderators

necropower
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,inicio;
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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
> long int max,k, i, q, j, maior , maior_n,fim,inicio;

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

[[]]'s Necropower

Ivan Golubev
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 necropower
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*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
New poster
Posts: 20
Joined: Wed Dec 26, 2001 2:00 am
i am becoming crazy with this prb.. i dont know where is my error... (

New poster
Posts: 4
Joined: Tue Feb 05, 2002 2:00 am
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,
In theory, there is no difference between theory and practice. But in practice, there is !

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

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
for t:=1 to N do begin
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
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

for casei:=1 to n do
begin
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
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

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

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

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
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
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:
You mean that you memorize the prime numbers before you calculate the numbers of divisors???

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
yes, I calculate all prime numbers from 2 to sqrt(1000*1000*1000) + 1000, before even reading input data

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm
*CUT*
Last edited by deddy one on Sun Oct 05, 2003 5:17 pm, edited 1 time in total.