Page 1 of 3

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

Posted: Mon Nov 26, 2001 12:50 pm
by ahanys
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>

Posted: Tue Dec 11, 2001 12:52 am
by chrismoh
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.

Posted: Sun Dec 16, 2001 6:06 pm
by ahanys
I get accepted.
Thank you

10061 WA

Posted: Sun Sep 21, 2003 4:59 pm
by mido
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]

Re: 10061 WA

Posted: Tue Nov 04, 2003 3:50 pm
by sergio
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 :)

10061 Test case correct?

Posted: Thu Mar 11, 2004 6:03 pm
by gagern
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[0]=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.

Posted: Thu Mar 11, 2004 7:08 pm
by Adrian Kuegel
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.

Posted: Wed Apr 14, 2004 6:49 pm
by gagern
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"...

Posted: Mon May 03, 2004 12:46 am
by mido
yup...that solved it...long time to reply...but thanks.... :wink:

Posted: Thu May 06, 2004 9:20 pm
by jamu
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?

Posted: Thu May 06, 2004 10:18 pm
by gagern
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.

Posted: Fri May 07, 2004 12:07 am
by jamu
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...

10061 How many zeros and how many digits?

Posted: Sun Dec 19, 2004 3:43 am
by Antonio Ocampo
Hi

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

Posted: Sun Dec 19, 2004 8:33 pm
by Antonio Ocampo
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

Posted: Wed Jan 05, 2005 7:55 pm
by Antonio Ocampo
Please, help me!!!!!!!!!!!! :(