10061 - How many zero's and how many digits ?

[little joey]

Code: Select all

joachim@joabox[p10061.cpl]$ a.out <test.txt
29262 398004
801 5973
19 75
4289 50675
754 102203
3204 35113
9 33
43 5631
joachim@joabox[p10061.cpl]$

[Antonio Ocampo]

Thanks for your reply Little Joey . I realized what my function to calculate how many zeros exist is wrong Would you mind telling me your algorithm???

Thanks in advance.

[little joey]

Count the number of occurences in N! of the prime factors of B.

Say N=33 and B=45. B=45 = 3^2 * 5, so the prime factors of B are 3 and 5.
Now count the number of occurences of 3 in 33!: 3, 6, 12, 15, 21, 24, 30 and 33 contribute one 3 each, 9 and 18 contribute two 3s each, and 27 contibutes three 3s, for a total of 15 threes.
Same for number of occurences of 5 in 33!: 5, 10, 15, 20 and 30 contibute one 5 each, 25 contibutes two 5s, for a total of 7 fives.
So we know 33! = ... * 3^15 * 5^7 * ...
The only way to get a zero in base 45 is to combine two 3s with one 5. This can be done a maximum of 7 times, so the number of zeros in 33! base 45 is 7.

Hope it helps,
-little joey

[Larry]

What's the answer for when N == 0? Any more critical cases? I keep getting WA.. I think I'm doing things right..

[sunnycare]

in this problem:

i use the formula:

n!=sqrt(2*pi*n)*[(n/e)^n];

to caculate the length of the n! (if in base k,then divide log(k))

i use a normal algorithm to caculate the trailing zero

here is my code:

Code: Select all

#include <iostream>
#include <cmath>

using namespace std;
#define N 800
#define ISPRIME(n) (!(prime[(n)>>4]&(1<<(((n)&15)>>1))))
#define MASK(n) (1<<(((n)&15)>>1))
unsigned char prime[N>>4];



//sieve prime from 1 to N
void sievePrimes()
{
	long i,j,k,l;
	
	for(i=0;i<=N>>4;i++)
		prime[i]=0;
	prime[0]++;
	
	
	k=long(sqrt(double(N)));
	for(i=3;i<=k;i+=2)
	{
		
		if(ISPRIME(i))
		{
			l=i<<1;
			
			for(j=i*i;j<=N;j+=l)
				prime[j>>4]|=MASK(j);
		}
	}
}
//get the totol number of the prime
long getTotolPrime()
{
	long i;
	long totol=1;
	for(i=3;i<N;i+=2)
	{
		if(ISPRIME(i))
		{
			//cout<<i<<endl;
			totol++;
		}
	}
	return totol;
}

void main()
{
	//n!=sqrt(2*pi*n)*[(n/e)^n];
	long primeTab[139];
	sievePrimes();
	long i,j;
	primeTab[0]=2;
	for(i=3,j=1;i<=800;i+=2)
	{
		if(ISPRIME(i))
			primeTab[j++]=i;
	}
	long min;
	double pi=2*acos(double(0.0));
	double e=exp(double(1.0));
	long a,b;
	long len;
	while(cin>>a)
	{
		cin>>b;
		len=floor((log(2*pi*a)/2+a*log(a/e))/log(double(b))+0.000001)+1;
		long tb=b;
		long ta;
		long times,count,tmp;
		min=999999999;
		for(i=0;i<139;i++)
		{
			times=0;
			count=0;
			ta=a;
			while(tb%primeTab[i]==0)
			{
				times++;
				tb=tb/primeTab[i];
			}
			if(times>0)
			{
				while(ta>0)
				{
					ta=ta/primeTab[i];
					count+=ta;
				}
				tmp=count/times;
				if(tmp<min)
					min=tmp;
			}
			if(tb<=1)
				break;
			
		}
		cout<<min<<' '<<len<<endl;
	}
		

}

[Antonio Ocampo]

I don

[GeorgeBusch]

There is nothing said about the case where N=0,
but I think you can assume that
0! = 1 should be taken and so there are no trailing zeroes and the length is one in every number system...

[Antonio Ocampo]

Well i have considered that case, but it doesn`t work

[Antonio Ocampo]

plz help me this problem is driving me mad. I have tested all I/O in the board but i still got WA. Thx a lot

[nymo]

input:

Code: Select all

2 9
100 23
23 101
23233 344
34 799

output:

Code: Select all

0 1
4 117
0 12
552 36014
0 14

[Antonio Ocampo]

Hi nymo thx for your reply . I got the same output with my WA code . So i'm posting it:

Code: Select all

Cut after AC :)

Please help me. This problem is driving me mad

Thx in advance

[nymo]

dear Antonio Ocampo,
I 've had several changes to your code to get ACC. I don't know what really 've mattered, but i did the following changes.

1. n is an unsigned number(20 bits)... don't know how long is int( may be its only 16bits, as i know ...), so, i changed it to long. for clarity i made all int to long.(for ease of use, i am used to long rather than int )

2.

Code: Select all

long veces(long n, long factor)(notice the changes in declaration, all is long now :))
{
    //int s=0;
    long s = 0;

    //while( n>=factor ) 
    while (n)  // I made a change here 
    {
      n/=factor;
      s+=n;
    }

    return s;
}

3.

Code: Select all

// int ceros(int n, int b)
long ceros (long n, long b)
{
   /*int*/long cantidad[139]={0},factor[139];
   /*int*/long t,i,j,min;

   for(j=0,i=0;b!=1;++i)
   {
     if( b%p[i]==0)
     {
       factor[j]=p[i];

       while(b%p[i]==0 && b>1)
       {
         ++cantidad[j];
         b/=p[i];
       }

       ++j;
     }
   }

   for(i=0,min=10000000l;i<j;++i) // some change in min value
   {
      t=veces(n,factor[i])/cantidad[i];

      if(t<min)
      {
       min=t;
      }
   }

   return min;
}

/*
I guess the value assigned in min may be bigger than the value that can be hold by an int, so, i made it long and i used the prefix "L" to denote it as long
*/

4.
For number of digits, i did the following:

Code: Select all

for(sum=0.0,i=1;i<=n;++i) // change in indexing
          sum+=(log10(i)/log10(b)); // change

         // cout<<ceros(n,b)<<" "<<int(floor(sum/log10(b)))+1<<"\n";
         cout<<ceros(n, b)<<" ";
         if (sum - floor(sum) < 1e-14)
         	sum ++;
         else
         	sum = floor(sum + 1);

         printf("%.0lf\n", sum);
      }

I am not used to C++ I/O, I use only C .so, I made the changes to my convenience..., however, it is ACC NOW , may be not all the changes did the trick, may be only one of them, but I don't want to find which one cause it already costs my some submissions ,

regards,
nymo

[Antonio Ocampo]

Thx a lot for sharing your great ideas !! I've just changed the initial value of min for 10000000 instead of 10000 and my output format(including the epsilon). And ........ finally I got AC .

Thx for helping me to finishing with this horrible nightmare
Keep posting.

PS Sorry for your lost submissions

[yiuyuho]

nvm, I am careless

[nukeu666]

ive tried all the inputs given on different threads here and tried using log10 in place of log, yet i get WA
for length ive done [sum of log(1...n)]/log(base)
for zeros ive calculated how many times the base perfectly divides number

Code: Select all

#include<iostream>
#include<cmath>
#include<vector>
int maxp(double n,double b) //to get max power of b in n for factorization
{
	int a=0;
	double s=b;
	while(int(n/s)!=0)
	{
		a+=int(n/s);
		s*=b;
	}
	return a;
}
using namespace std;
int main()
{
        if(n==0)
	    {cout<<"0 0"<<endl;continue;}
	double n,b;
	vector<long> pr;//list of primes below 300
	pr.push_back(2);
	pr.push_back(3);
	pr.push_back(5);
	pr.push_back(7);
	pr.push_back(11);
	pr.push_back(13);
	pr.push_back(17);
	pr.push_back(19);
	pr.push_back(23);
	pr.push_back(29);
	pr.push_back(31);
	pr.push_back(37);
	pr.push_back(41);
	pr.push_back(43);
	pr.push_back(47);
	pr.push_back(53);
	pr.push_back(59);
	pr.push_back(61);
	pr.push_back(67);
	pr.push_back(71);
	pr.push_back(73);
	pr.push_back(79);
	pr.push_back(83);
	pr.push_back(89);
	pr.push_back(97);
	pr.push_back(101);
	pr.push_back(103);
	pr.push_back(107);
	pr.push_back(109);
	pr.push_back(113);
	pr.push_back(127);
	pr.push_back(131);
	pr.push_back(137);
	pr.push_back(139);
	pr.push_back(149);
	pr.push_back(151);
	pr.push_back(157);
	pr.push_back(163);
	pr.push_back(167);
	pr.push_back(173);
	pr.push_back(179);
	pr.push_back(181);
	pr.push_back(191);
	pr.push_back(193);
	pr.push_back(197);
	pr.push_back(199);
	pr.push_back(211);
	pr.push_back(223);
	pr.push_back(227);
	pr.push_back(229);
	pr.push_back(233);
	pr.push_back(239);
	pr.push_back(241);
	pr.push_back(251);
	pr.push_back(257);
	pr.push_back(263);
	pr.push_back(269);
	pr.push_back(271);
	pr.push_back(277);
	pr.push_back(281);
	pr.push_back(283);
	pr.push_back(293);

	while(cin>>n>>b)
	{
		double factl=0,base=b;
		for(long t1=1;t1<=n;t1++)
			factl+=log10(t1);
		vector<long> bfact;
		vector<long> nfact;
		vector<long>::iterator r;
		vector<long>::iterator t;
		for(r=pr.begin();r!=pr.end();r++) //factorizing the base
		{
			long f=0;
			while(b==long(b/(*r))*(*r))
			{
				f++;
				b=b/(*r);
			}
			bfact.push_back(f);
		}
		r=pr.begin();
		while((*r)<=n&&r!=pr.end())//factorizing the number
		  {
		    nfact.push_back(maxp(n,(*r)));
		    r++;
		  }
		while(nfact.end()-nfact.begin()!=bfact.end()-bfact.begin()) //making the array lengths equal
		      nfact.push_back(0);
		t=nfact.begin();
		r=bfact.begin();
		long min=*t; //taking one of the values as starting minimum value
		long tmp=min;
		while(r!=bfact.end()&&t!=nfact.end()) //checking how many times the base perfectly divides number
		  {
		    long div;
		    if((*r)==0&&(*t)==0)
		      {div=tmp;}
		    else if((*r)==0&&(*t)!=0)
		      {div=tmp;}
		    else if((*t)==0&&(*r)!=0)
		      div=0;
		    else
		      div=(*t)/(*r); //finding minimum times a prime factor of base can divide number
		    t++;r++;
		    if(div<min)
		      min=div;
		  }		
		cout<<min<<" "<<long(factl/log10(base))+1<<endl;
	}
}

heres the output if i print the factors also
input/factors of base/factors of n!/answer

40 8
3 0 0 0 0 0 0 0 0 0 0 0 0 ....
38 18 9 5 3 3 2 2 1 1 1 1 ....
12 54

600 30
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
596 297 148 98 58 49 37 32 27 20 19 16 14 13 12 11 10 9 8 8 8 7 7 6 6 5 5 5 5 5 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
148 954