Page 3 of 3

Posted: Tue Aug 01, 2006 11:59 pm
by Sedefcho
To nymo: thanks a lot from me.
I started attacking this problem today and
your post was crucial for solving it. After
about 15 submissions I got ACC.

Here is some more input from me for anyone who
might still be trying to solve it.
Note: 1048575 = 2^20 - 1, this according to the
problem statement is the largest number allowed
in the input as a value for N.

INPUT

Code: Select all

0 2
1 2
2 9 
100 23 
23 101 
23233 344 
34 799 
1000000 799
1000010 800
1048575 2
1048575 3
1048575 17
1048575 101
1048575 799
1048575 800

OUTPUT

Code: Select all

0 1
0 1
0 1
4 117
0 12
552 36014
0 14
21737 1917527
125000 1917188
1048555 19458736
524281 12277096
65533 4760591
10484 2922517
22794 2018112
131070 2017734
Good luck to everyone!

WA in 10061

Posted: Tue Aug 22, 2006 9:30 pm
by shihabrc
Getting WA in this prob. My code passed all the inputs posted in the prev posts. I still don't know my fault. I'm giving my code.

Code: Select all


Cut after AC


Posted: Tue Aug 22, 2006 10:27 pm
by yiuyuho
change
digit=floor(logarithm/log10(base))+1;
to
digit=floor(logarithm/log10(base)+1e-9)+1;

Yes, watch them floats!

Posted: Wed Aug 23, 2006 3:59 pm
by shihabrc
Thanx. Got AC NOW. :D.

Posted: Wed Aug 23, 2006 9:42 pm
by yiuyuho
no problem, my brother in a distant land!

Posted: Tue Dec 04, 2007 9:43 pm
by srrajesh
nymo wrote: dear Antonio Ocampo,
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);
      }
Indeed, this helped me a lot!
Though, my code works with all the test case in this forum, I think there should be some sort of rounding off error, which produced WA!
When I added checking with "epsilon" 1e-14, as in your code, I got AC.
Thanks a lot.

But I am curious to know, what test case necessiates such a checking.
The test cases given in this thread don't need such a checking!
I really want to see such a test case, because I suffered a lot of WAs owing to that! :)

Re: 10061 - How Many Zeros and How Many Digits?

Posted: Sun Aug 17, 2008 12:39 pm
by rhsumon
Where is the problem i cannot find
plz help some one
here is my code:

Code: Select all

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

#define P 2005
#define M 1050000

long prime[P]; 
long p[500];
double f[500]; 

void gen_prime(){
	int i,j;
	prime[0] = prime[1] = 1;
	for(i=2; i<=(long)sqrt(P); i++){
		if(prime[i]==0){ 
			for(j=i*i; j<=P-1; j=j+i){
				prime[j]=1;
			}
		}
	} 
	j=0; 
	for(i=0; i<=P-1; i++){ 
		if(prime[i] == 0){
			p[j] = i;
			f[j++]=0;
		}
	}
}

double tzero(int n,int b){
	int i=0,j,nn;
	while(b!=1){
		while(b%p[i]==0){
			f[i]++;
			b/=p[i];
		}
		i++;
	}
	double sum,min=M;
	for(j=0; j<i; j++){
		nn=n;
		sum=0;
		if(f[j]!=0){
			while(nn!=0){
				sum+=nn/p[j];
				nn/=p[j];
			}
			if(min > sum/f[j])
				min=sum/f[j];
			f[j]=0;
		}
	}
	return floor(min);
		
}

double tdigit(int n,int b){
	double sum;
	int i;
	if(n==0) return 1;
	else{
		sum=0;
		for(i=1;i<=n;i++){
			sum+=log10(i)/log10(b);
		}
		return floor(sum)+1;
	}	
}

int main()
{
	freopen("10061.out","w", stdout);
	gen_prime();
	double zcount,dcount;
	int n,b;
	while(scanf("%d%d",&n,&b)==2){
		zcount=tzero(n,b);
		dcount=tdigit(n,b);
		printf("%.0f %.0f\n",zcount,dcount);
	}
	return 0;
}

Plz take a look anybody.......... :cry: 

Re: 10061 - How Many Zeros and How Many Digits?

Posted: Wed Dec 31, 2008 11:56 pm
by amishera
I read the above posts and tested all the inputs and also changed some modifications suggested in prior posts. The outputs seem to agree on the answers provided but the same wrong answer.

Code: Select all

#include <stdio.h>
#include <math.h>

#define MAX_LONG 2147483647

int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547,
557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797};

int maxPower(int n, int p)
{
	int power = p;
	int mp = 0;
	int tn = n;
	while (tn % power == 0)
	{
		mp++;
		power *= p;
	}
	return mp;
}

unsigned long maxFactorialPower(unsigned long n, int p)
{
	unsigned long power = p;
	unsigned long sum = 0;
	while (n >= power)
	{
		sum += n/power;
		power *= p;
	}
	return sum;
}


int main()
{
	unsigned long n;
	int b,i, mp;
	double pi=2*acos(double(0.0));
	double e=exp(double(1.0));

	unsigned long mfp;
	while (scanf("%lu %d",&n,&b) != EOF)
	{
		unsigned long nDigit, nZero = MAX_LONG;
		for (i = 0;i < 139;i++)
		{
			if (b < primes[i])
				break;
			if (b % primes[i] == 0)
			{
				mp = maxPower(b,primes[i]);
				mfp = maxFactorialPower(n,primes[i]);
				unsigned long tnd = mfp/mp;
				if (tnd < nZero)
					nZero = tnd;
			}
		}
		double num = 0;

		/*for (i = 1;i <= n;i++)
		{
			num += log(i);
		}

		double denom = log(b);*/
		if (n == 0 || n == 1)
		{
			printf("0 1\n");
		}
		else {
			nDigit = floor((log(2*pi*n)/2+n*log(n/e))/log(double(b))+0.000001)+1;
			printf("%lu %lu\n",nZero,nDigit);
		}
	}
	return 0;
}
Some suggestion please.

Re: 10061 - How Many Zeros and How Many Digits?

Posted: Sun Dec 20, 2009 12:45 pm
by SeregiB
Hi!

Any idea, what is wrong with this code?

Code: Select all

#include <stdio.h>
#include <limits.h>
#include <math.h>
#include <stdlib.h>
unsigned int digits(unsigned int n, unsigned int base)
{
  return (unsigned int)(floor((log10(2*M_PI*n)/2+n*(log10(n)-log10(M_E)))/log10(base)+1e-9)+1);
}
unsigned int legendre(int n, int p)
{
	long long int i, log_p_n = (int)(log10(n) / log10(p)), summa = 0;
	for(i = 1; i <= log_p_n; i++)
	{
		summa += (long long int)floor(n/pow(p,i));
	}
	return summa;
}
unsigned int zeros(unsigned int k, unsigned int num)
{
  unsigned int * exp;
  unsigned int t[34] = {0}, min = LONG_MAX;
  exp = (unsigned int*)malloc(1048600);
  unsigned int i = 0, c = 0, d = 2, j;
  while(k > 1)
	{
    if(k % d == 0)
		{
      k /= d;
			if(t[i-1] != d)
			{
      	t[i] = d;
      	i++;
			}
			exp[d]++;
    }
    else d++;
  }
  for(j = 0; j < i; j++)
	{
		k = legendre(num,t[j]) / exp[t[j]];
		if(k < min) min = k;
  }
  return min;
}
unsigned int n = 0, base, z;
int main()
{
	while(scanf("%d %d",&n,&base) != EOF)
	{
		z = digits(n,base);
		if(!z) z = 1;
		printf("%d %d\n",zeros(base,n),z);
	}
  return 0;
}
I have tried out with many test cases and I got right results, so I do not understand what is the problem.

Re: 10061 - How Many Zeros and How Many Digits?

Posted: Sat Sep 10, 2011 4:37 pm
by Ahmad
there is a very simple Algorithm to get the number of zeros without making any prime factoring ...
All what we have to do is finding how many times the base divides the factorial ... we can do it in O(n) but we will have to avoid the overflow ...
that's where the modulus part comes ... and i will let you think about this number (the Mod)
Hint : (think about finding the last nonzero digit in decimal for a factorial)

Re: 10061 - How Many Zeros and How Many Digits?

Posted: Sun May 27, 2012 3:15 pm
by magurmach
Getting WA in this problem...

PLZ PLZ Help!

Code Link: Code removed after AC


Thanks in advance!

Re: 10061 - How Many Zeros and How Many Digits?

Posted: Fri Jun 01, 2012 1:17 am
by brianfry713
It looks like you figured it out.

Re: 10061 - How Many Zeros and How Many Digits?

Posted: Mon Jun 11, 2012 10:24 am
by magurmach
If getting WA then most possibly the cause is precision
The problem is in digit calculation. Problem is not in formula but precision. add 1e-9 before converting double to long or the format used! Many problems will be solved!

A hard test case

Posted: Fri Jul 10, 2015 3:01 am
by ryx
You can try this case
41 26