Page 4 of 7

294 WA

Posted: Wed Aug 24, 2005 11:59 am
by abyss
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;
           }                 
                 
            

Posted: Wed Aug 24, 2005 12:47 pm
by abyss
finally got accepted

294 TLE,dunno why

Posted: Sat Oct 15, 2005 4:47 am
by thirddawn
#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...

Posted: Sat Oct 15, 2005 8:42 am
by Timo
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.

Posted: Sat Nov 12, 2005 6:58 pm
by marcadian
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"

Posted: Sat Nov 12, 2005 7:54 pm
by angga888
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:

Posted: Tue Nov 15, 2005 7:56 am
by marcadian
hm... but i sill got WA, could someone give me test case ??

how could this be?

Posted: Sat Dec 24, 2005 8:32 am
by plankton
Did I miss something or what?
How could a number have only one divisor ?? *~*

Re: how could this be?

Posted: Sat Dec 24, 2005 1:16 pm
by mamun
plankton wrote:How could a number have only one divisor ?? *~*
How many divisors 1 has got?

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

Posted: Thu Mar 23, 2006 12:25 pm
by Staryin

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;	
}

259 -- Divisors, How to speed things up?

Posted: Tue Apr 18, 2006 9:22 pm
by RajivMathews
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.

294 - WA

Posted: Thu Nov 09, 2006 12:03 pm
by Tine
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

Posted: Thu Nov 09, 2006 12:22 pm
by DIR EN GREY
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

Posted: Fri Nov 10, 2006 5:37 pm
by Tine
Yeah, that was my problem

Thank you!

Posted: Sun Mar 11, 2007 3:21 pm
by newton
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