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

Post by abyss » Wed Aug 24, 2005 11:59 am

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

Post by abyss » Wed Aug 24, 2005 12:47 pm

finally got accepted

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

294 TLE,dunno why

Post by thirddawn » Sat Oct 15, 2005 4:47 am

#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

Post by Timo » Sat Oct 15, 2005 8:42 am

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:

Post by marcadian » Sat Nov 12, 2005 6:58 pm

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"

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Sat Nov 12, 2005 7:54 pm

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'. :wink:

marcadian
New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

Post by marcadian » Tue Nov 15, 2005 7:56 am

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?

Post by plankton » Sat Dec 24, 2005 8:32 am

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?

Post by mamun » Sat Dec 24, 2005 1:16 pm

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?!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Post by Staryin » Thu Mar 23, 2006 12:25 pm

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?

Post by RajivMathews » Tue Apr 18, 2006 9:22 pm

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

Post by Tine » Thu Nov 09, 2006 12:03 pm

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

Post by DIR EN GREY » Thu Nov 09, 2006 12:22 pm

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

Post by Tine » Fri Nov 10, 2006 5:37 pm

Yeah, that was my problem

Thank you!

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

Post by newton » Sun Mar 11, 2007 3:21 pm

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

Post Reply

Return to “Volume 2 (200-299)”