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

Moderator: Board moderators

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

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

May somebody please explain me how to solve this problem. I solved a problem 453 and I help you.

<font size=-1>[ This Message was edited by: ahanys on 2001-12-06 14:13 ]</font>

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA
Hi,

I think I'll try 453 on my own, thanks anyway.

for 10061, there are 2 parts:

(1) Find number of trailing zeroes

Factorize the base and the factorial. Actually you don't have to factorize the factorial completely. Just calculate the prime factors present in the base.

e.g. in base 10, 10 = 2 * 5
100! contains:
2^(some number that I didn't compute) * 5 ^ 24. Obviously, 5 is the limiting factor here and thus the number of trailing zeroes is 24. (Other prime factors not in base are not important).

(2) Find number of digits in base representation

Use log. When logged by a certain base, you will get the number of digits in the representation of the number in that base (round down).

e.g. log (base 10) 89 = 2.???, therefore the number of digits is 2 (for 89 represented in decimal).

Two basic identities:

log (base x) (some_value) = ln (some_value) / ln x (ln = natural log)

log ab = log a + log b
(naturally implies log n! = log 1 + log 2 + log 3 + log 4 + ... + log n which is one way to attack this problem)

I hope this helps.

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:
I get accepted.
Thank you

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

### 10061 WA

Anything wrong here...I tested it as much as I could :
[cpp]
#include <iostream.h>
#include <math.h>
#include <stdio.h>

long i,zeroes,n,b,prod;
double log_res;

void main()
{
while (cin>>n>>b)
{
zeroes=0;
prod=1;

for (i=1;i<=n;i++)
{
prod*=i;
while (prod%b==0) {zeroes++;prod/=b;}
prod%=b;
}

log_res = 0;

for (i=1;i<=n;i++)
{
log_res+=log10(i)/log10(b);
}

if (log_res - floor(log_res)<1e-14)
log_res++;
else
log_res = floor(log_res + 1);

printf("%ld %.0lf\n",zeroes,log_res);

}
}
[/cpp]

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:

### Re: 10061 WA

Hi, mido!

I think your mistake is when you are trying to find how many trailing zeros the factorial has in the base b, the other part is ok Try this:

Input
1000000 798
1000000 799

Output
55553 1917886
21737 1917527

Your program's output was different of the my accept's problem output. Try to find how many trailing zeros the factorial of the number has without do multiplications, only using how many prime factors of the base the factorial of the number has.
I hope that you understand my explanation gagern
New poster
Posts: 7
Joined: Thu Mar 11, 2004 5:37 pm

### 10061 Test case correct?

Hello!

First thing: after the following code I'm going to discuss different solution strategies, so if you want to think for yourself, please don't read on. But this code is fine to use, since it is way too slow for the judge. But it does create exact results, since it really calculates the factorial. You will need GCC and at least an 386 processor. And very much time.

[c]
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define STEP (1024*1024)
#define INITIAL (4*STEP)

int main() {
int n, b, capacity=INITIAL;
unsigned short *digits=(unsigned short*)malloc(INITIAL*2);
if (digits==NULL) {
perror("initial malloc");
return 2;
}
while (scanf(" %d %d", &n, &b)==2) {
unsigned length=1, zeros, carry, i, j;
char status[]="|= |%3.0f%% %7d %8d\r";
digits=1;
for (i=2; i<=n; ++i) {
asm ("movl %4, %%ecx \n\t" /* counter=length */
"xorl %0, %0 \n0:\t" /* carry=0 */
"movzwl (%3), %%eax \n\t" /* eax=*digit */
"mull %1 \n\t" /* edx:eax=eax*i */
"addl %0, %%eax \n\t" /* eax+=carry, set CF */
"movl \$0, %0 \n\t" /* carry=0 */
"adcl %0, %%edx \n\t" /* edx+=CF */
"divl %2 \n\t" /* eax=edx:eax/b */
"movw %%dx, (%3) \n\t" /* *digit=edx:eax%b */
"addl \$2, %3 \n\t" /* ++digit */
"movl %%eax, %0 \n\t" /* carry=eax */
"loop 0b \n" /* while(--counter) */
: "=&r" (carry)
: "g" (i), "g" (b), "r" (digits), "m" (length)
: "%eax", "%ecx", "%edx");
while (carry) {
if (length==capacity) {
unsigned short* nd;
capacity+=STEP;
nd=(unsigned short*)realloc(digits, capacity*2);
if (nd==NULL) {
perror("realloc");
free(digits);
return 3;
}
digits=nd;
}
digits[length++]=carry%b;
carry/=b;
}
for (j=(long long)i*i*32LL/n/n+1; status[j]==' '; --j) status[j]='=';
fprintf(stderr, status, 100.*i*i/n/n, i, length);
}
for (zeros=0; digits[zeros]==0; ++zeros);
for (j=0; status[j]!='\r'; ++j);
status[j]='\n';
fprintf(stderr, status, 100., n, length);
fflush(stderr);
printf("%d %d\n", zeros, length);
fflush(stdout);
}
return 0;
}
[/c]

I believe it should be possible to use lgamma to calculate the number of digits. I did this and got WA. I then wrote another version which did sums of logarithms, and this one was accepted.

Then I created a program that generates random test cases and compares the results from both. There were extremely few differences (only 8 in 500 million test cases). I was curious which one would be correct, so I wrote the program above. So far I got results for two of my random cases:

345900! in base 195 has 771039 digits (not 771038)
647169! in base 374 has 1352439 digits (not 1352440)

In both cases, the correct result was also calculated by lgamma, but not by the sum of logarithms. So if the program that generated correct values for me got a "Wrong Answer", and the program that created some few wrong results was accepted, maybe there is something wrong with the test case used by the online judge.

Maybe someone who has access to the test case can pick out the cases where small floatingpoint differences might lead to different integer results and feed those cases to the above program or simply remove them.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
I used also a program that calculates the result as sum of logarithms, but I get the correct result for the 2 test cases you mentioned.
Maybe someone who has access to the test case can pick out the cases where small floatingpoint differences might lead to different integer results and feed those cases to the above program or simply remove them.
You can send a mail to problemset@acm.uva.es. Best thing would be to attach both of your programs and ask if they could send you the test cases where your output differs, then you could check the output for these test cases. But I think that using lgamma may lead to more precision errors than using sum of logarithms, at least I can remember that for one problem where I used it I had to make some special cases to get correct answers.

gagern
New poster
Posts: 7
Joined: Thu Mar 11, 2004 5:37 pm
I did so and together with Carlos we found that lgamma is not part of ANSI C and was therefore not declared, so my program tried to pass the parameter as an integer. That happens if you don't compile with "-ansi -Wall"...

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
yup...that solved it...long time to reply...but thanks.... jamu
New poster
Posts: 13
Joined: Wed Dec 03, 2003 11:15 am
Hi,

I used sum of logarithms to find how many digits the factorial has and used the formula:
log_a(b) = log_c(b) / log_c(a)
where log_x(y) is the logarithm of y relative to the base x
you can use any c > 0, c != 1 to find a logarithm of b to the "strange" base a.

program which uses natural logarithms gets "Wrong Answer" from the judge while program with logarithms to the base 10 gets "Accepted".

different bases can lead to different answers because of precission of floating point representation (however I've tested it with over 2,000,000 of randomly generated test cases and programs with log_10 and natural log have given the same answers)

I think judge's test cases were generated by the program which uses log_10, so judge accept programs with log_10 and gives WA to all with natural logarithms. Naturally I may be wrong.

Anybody who used natural logarithms got Accepted?

gagern
New poster
Posts: 7
Joined: Thu Mar 11, 2004 5:37 pm
I have a Program using natural logarithm that gets accepted.

But I have to apply a little bit of correction, because when the actual result is very close to an integer, numeric error might lead to the number being actually rounded to an integer one too small. So I add 1e-14 and it works.

jamu
New poster
Posts: 13
Joined: Wed Dec 03, 2003 11:15 am
So I'am wrong.
I submitted my program (using C function log()) with many different floating point correction and without any correction and it always got WA. Then I only changed log() to log10() and it recived Accepted (without any special correction). Strange...

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

### 10061 How many zeros and how many digits?

Hi

Could someone give me critical I/O??? I got WA but I don

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Could someone confirm this output??

Input

234124 800
3213 45
23 2
34325 600
66436 712
25645 800
21 4
3443 79

Output
7551 398004
400 5973
19 75
1429 50675
754 102203
826 35113
6 33
43 5631

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Please, help me!!!!!!!!!!!! 