294 - Divisors

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

why do i keep getting WA's

#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 · Post by **abyss** » Wed Aug 24, 2005 12:47 pm

finally got accepted

thirddawn · 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 · 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 · 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"

angga888 · 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'.

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

hm... but i sill got WA, could someone give me test case ??

plankton · 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 · 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 · 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 · 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 · 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 · 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

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

Yeah, that was my problem

Thank you!

newton · 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

OJ Board

294 - Divisors

294 WA

294 TLE,dunno why

how could this be?

Re: how could this be?

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

259 -- Divisors, How to speed things up?

294 - WA