## 294 - Divisors

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

Moderator: Board moderators

abyss
New poster
Posts: 3
Joined: Wed Aug 24, 2005 8:03 am

### 294 WA

why do i keep getting WA's

Code: Select all

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

int main()
{
int no,i,nodiv,total=1,max=0;
long int n1,n2,k,n,j,number,numbers;
scanf("%d",&no);

for(i=0;i<no;i++)
{
scanf("%ld %ld",&n1,&n2);
max=0;
for(k=n1;k<=n2;k++)
{
n=k;
total=1;

for(j=2;j<=sqrt(n)+1;j++)
{
nodiv=1;
while(!(n%j))

{
nodiv++;
n/=j;
}
total*=nodiv;
}
if(n!=1)
total*=2;
if(total>max)
{
max=total;
number=k;
}
}

printf("Between %ld and %ld, %ld has a maximum of %d divisors.\n",n1,n2,number,max);
}

return 0;
}

``````

abyss
New poster
Posts: 3
Joined: Wed Aug 24, 2005 8:03 am
finally got accepted

thirddawn
New poster
Posts: 9
Joined: Sat Oct 15, 2005 4:41 am

### 294 TLE,dunno why

#include <stdio.h>

int main(){
int i=0,a,b,ba,b0,c,d,e=0,e0=0;
int j;
scanf("%d",&a);
for (i=1;i<=a;i++){
scanf("%d%d",&b,&c);
b0=b;
for (j=b;j<=c;j++){
e=0;
for (d=j;d>=1;d--){
if (j%d==0)
e=e+1;
if (e0<e){
e0=e;
ba=j;
}
}
}
printf("Between %d and %d, %d has a maximum of %d divisors.",b0,c,ba,e0);
}
return 0;
}

thanks for viewing my program...

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia
Suppose N is an integer that we want to know how many divisors that it has.
I see that your algo is :

j=N;
c=0;
loop from j decrease to 1
if N mod j
then c=c+1;

you should not use the above method because it too slow for this problem.

I will give you a little hint.

if N=8 then c=4
there are 4 integer can divide 8, they are 1,2,4,8.
because N=2^3
c=(3+1) = 4

if N=24 then c=8
there are 8 integer can divide 24, they are 1, 2, 3, 4, 6, 8, 12, 24
because N=(2^3) * (3^1)
c=(3+1)*(1+1)=8

if N is a prime number then c=2
because prime number only have 2 divisors : 1 and N.

so the number of divisors of N can be found by :

N=(a^i)*(b^j)*(c^k)
c=(i+1)*(j+1)*(k+1)

where i,j,k are prime factor from N.
you only need to find prime factor below sqrt(N).
this method will be able to pass the time limit.

I hope you will get AC.

marcadian
New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:
I always get WA in this prob. Could someone give me tricky test case??
If number only has 1 divisor, should i output "bla bla bla has 1 divisor" or "bla bla bla has 1 divisors"

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
marcadian wrote:If number only has 1 divisor, should i output "bla bla bla has 1 divisor" or "bla bla bla has 1 divisors"
According to the problem description:
Print the text 'Between L and H, P has a maximum of D divisors.', where L, H, P, and D are the numbers as defined above.
I think the output should still be 'bla bla bla has 1 divisors'.

marcadian
New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:
hm... but i sill got WA, could someone give me test case ??

plankton
New poster
Posts: 3
Joined: Sun Sep 11, 2005 11:07 pm

### how could this be?

Did I miss something or what?
How could a number have only one divisor ?? *~*

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

### Re: how could this be?

plankton wrote:How could a number have only one divisor ?? *~*
How many divisors 1 has got?

Staryin
New poster
Posts: 12
Joined: Fri Dec 16, 2005 4:22 pm
Location: shanghai/china
Contact:

### 294 WA who can HELP ME?!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Code: Select all

``````#include<iostream>
#include<cmath>
using namespace std;
int num;
long long low,upper,index;
long long i,j,k,b;
long long  divi,di;
void print()
{

cout<<"Between "<<low<<" and "<<upper<<", "<<
index<<" has a maximum of "<<divi<<" divisors."<<endl;

}

void solve()
{

divi=index=0;
for(i=low;i<=upper;i++)
{
b=i;k=2;j=0;di=1;
while(k<=sqrt(i*1.0))
{
if(b%k==0)
{
b=b/k;
j++;
continue;
}
if(j>=1)
di*=(j+1);
k++;j=0;
}

if(b>1 && b<i)
di*=2;

/*	if(b==i&&i!=1)
{
divi=1;
index=i;

}
*/
if(di>divi)
{
divi=di;
index=i;
}

}

}
void read()
{
int loop;
cin>>num;
for(loop=0;loop<num;loop++)
{
cin>>	low >> upper;
solve();
print();
}

}
int main()
{

read();
return 0;
}
``````

RajivMathews
New poster
Posts: 1
Joined: Tue Apr 18, 2006 7:59 am

### 259 -- Divisors, How to speed things up?

I got an AC on problem 259, Divisors, BUT I noticed hundreds
of users on the stats page with CPU times like 0:00.000(!!), whilst
mine was 7.352!!
I was wondering if the guys who got these *incredible* runtimes
could share their algo here...
I used the standard method,
N = p1^i * p2^j * ... * pn^k then N has (i+1)*(j+1)*...*(k+1) divisors.
I used sieve to find primes till 33000 (approx sqrt of the limit) [Athough
this couldn't have been the bottleneck]
Any better methods will be appreciated.

Tine
New poster
Posts: 2
Joined: Thu Nov 09, 2006 11:58 am

### 294 - WA

Hi..

I can't figure which input data gives me the WA. Everything I try gives me a correct answer. Am I missing something?

Code: Select all

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

using namespace std;

#define F     1000000000
#define N ((long) sqrt(F))
#define SQRTN ((long) sqrt(N))

vector<int> primefactors(int a,int* prime)
{
vector<int> primefactors;
for(int i=1; i<=a; ++i)
{
if(i>N+1)
{
primefactors.push_back(a);
break;
}
if(a%i==0 && prime[i])
{
primefactors.push_back(i);
a=a/i;
i=1;
}
}
return primefactors;
}

main(void)
{
int n, I, K, x, y, rez, rezTmp, tmp, max, maxSt;
vector<int> faktorji;
vector<int>::iterator i;

int  prime[N+1];
long M;
long S;

prime[0] = 0;
prime[1] = 0;
for (M = 2; M <= N; M++)
prime[M] = 1;

for (M = 2; M <= SQRTN; M++)
if (prime[M])
for (S= 2; S <= (N / M); S++)
prime[S * M] = 0;

scanf(" %d", &n);

for(I=0; I<n; I++)
{
scanf(" %d %d", &x, &y);
rez=1;rezTmp=0;
max=0;
for(K=x; K<=y; K++)
{
rez=1;
rezTmp = 1;
tmp = K;
faktorji = primefactors(K,prime);
for(i = faktorji.begin(); i!=faktorji.end();i++)
{
if(*i!=*(i+1))
{
rez*=(rezTmp+1);
rezTmp=1;
}
else
{
rezTmp++;
}
}
if(max<rez)
{
max = rez;
maxSt = K;
}
}
printf("Between %d and %d, %d has a maximum of %d divisors.\n", x, y, maxSt, max);
}

return 0;
}
``````
Thanks for the help

DIR EN GREY
New poster
Posts: 12
Joined: Thu Nov 09, 2006 11:49 am
Hi.

Try following input, you'll get correct output.

Code: Select all

``````2
2 2
100 100
``````
But another following input, you'll get incorrect output.

Code: Select all

``````2
100 100
2 2
``````
maybe there is a little bug
Do you understand my English???

Tine
New poster
Posts: 2
Joined: Thu Nov 09, 2006 11:58 am
Yeah, that was my problem

Thank you!

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:
dear staryin

dont make any new threat before searching all information about the problem you face.you have not mentioned what type of problem you are facing?
clarify it.

if it is TLE.
try to avoid using functions.
it will eat your time.

newton................ simply the best