10061 - How many zero's and how many digits ?
Moderator: Board moderators
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>
<font size=-1>[ This Message was edited by: ahanys on 2001-12-06 14:13 ]</font>
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.
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.
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]
[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
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
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?
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.
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.
-
- 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.
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.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.
Hi,
I used sum of logarithms to find how many digits the factorial has and used the formula:
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?
I used sum of logarithms to find how many digits the factorial has and used the formula:
you can use any c > 0, c != 1 to find a logarithm of b to the "strange" base a.log_a(b) = log_c(b) / log_c(a)
where log_x(y) is the logarithm of y relative to the base x
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?
-
- 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
Could someone give me critical I/O??? I got WA but I don
-
- Experienced poster
- Posts: 131
- Joined: Sat Jul 17, 2004 4:09 am
- Location: Lima, Per
-
- Experienced poster
- Posts: 131
- Joined: Sat Jul 17, 2004 4:09 am
- Location: Lima, Per