Problem 3

points - 15

The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example,
5! = 1 x 2 x 3 x 4 x 5 = 120
BUt this is in decimal number system. 10! can be written as 3628800 in decimal number system while it is equal to "15657400" in octal number system and "375F00" in hexadecimal number system.
Let NOZ(N,B) be a function which calculates the number of trailing zeroes that are in N factorial in a Base B number system. Therefore, NOZ(10,8) = NOZ(10,10) = NOZ(10,16) = 2.
Find .

Answer

23054122

Solution

We can always represent B as a product of primes as
B = a^p1 * b^p2 * c^p3 * ...
Then the number of trailing zeroes in n factorial in Base B is given by the formulae
min{1/p1(n/a + n/(a*a) + ....), 1/p2(n/b + n/(b*b) + ..), ....}.

Here is the C++ code:

#include<iostream>
using namespace std;
#include<math.h>
int main()
{
    int N,B,i,j,p,c,noz,k,sum=0;
    for (N=2;N<=1000;N++)
        for (B=2;B<=1000;B++)
        {
            noz=N;
            j=B;
            for (i=2;i<=B;i++)
            {
                if (j%i==0)
                {   
                    p=0;
                    while (j%i==0)
                    {
                          p++;
                          j/=i;
                    }
                    c=0;
                    k=N;
                    while (k/i>0)
                    {
                          c+=k/i;
                          k/=i;
                    }
                    noz=min(noz,c/p);
                }
          }
          sum+=noz;
    }
    cout<<sum;
}