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

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
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???

Last edited by Antonio Ocampo on Sat Jan 08, 2005 1:22 am, edited 2 times in total.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
What's the answer for when N == 0? Any more critical cases? I keep getting WA.. I think I'm doing things right..

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

### 10061 need some samples

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))))
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)
}
}
}
//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++;
}
}
}

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
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
I don

GeorgeBusch
New poster
Posts: 10
Joined: Fri Jun 10, 2005 5:30 pm
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
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Well i have considered that case, but it doesn`t work

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
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
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### Some more i/o:

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
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
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 :)
``````

Last edited by Antonio Ocampo on Tue Nov 01, 2005 5:11 am, edited 1 time in total.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)
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 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)
{
b/=p[i];
}

++j;
}
}

for(i=0,min=10000000l;i<j;++i) // some change in min value
{

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
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
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
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
nvm, I am careless

nukeu666
New poster
Posts: 44
Joined: Sun Feb 13, 2005 1:13 am
Location: India
Contact:

### 10061

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