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

[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>

[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.

[ahanys]

I get accepted.
Thank you

[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]

[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

[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.

[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.

[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"...

[mido]

yup...that solved it...long time to reply...but thanks....

[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?

[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.

[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...

[Antonio Ocampo]

Hi

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

[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

[Antonio Ocampo]

Please, help me!!!!!!!!!!!!