Given an integer 1 <n <10 ^ 9. You need to write a C ++ program that looks for the number of zeros in the number n! in the number system 225. We need some kind of clever algorithm, so as not to look for the factorial itself, because it is huge.

  • one
    Perhaps the number of zeros at the end of the number? - Chorkov
  • I feel an attempt to calculate the factorial N=10^9-1 will end very quickly OutOfMemoryException :) - teran
  • @teran If I'm not mistaken, 9 gigabytes should be enough for recording :) - Harry
  • More generally it was here - Yuri Negometyanov

2 answers 2

You need to essentially calculate what degree 255 divides the number n! Since the decomposition of 225 into prime factors is 5² × 3², you need to calculate degree 5 and degree 3 into which your number is divided.

According to Wikipedia , the degree k prime number p into which n! is divided n! is calculated as:

 int maxPowerOf(int p, int n) { int k = 0; int powerOfP = 1; while (true) { powerOfP *= p; int addend = n / powerOfP; if (addend == 0) return k; k += addend; } }

With this, you calculate your degrees:

 int p3 = maxPowerOf(3, n); int p5 = maxPowerOf(5, n);

Degrees of numbers 9 and 25, into which n! is divided n! equal respectively

 int p9 = p3 / 2; int p25 = p5 / 2;

(since 25 = 5² and 9 = 3²), and the desired power of the number 225, into which n! is divided n! , there is

 min(p9, p25)

While I was writing the answer, @Harry had already written the same thing. I leave only because of the code.

  • It can be mentioned that min(p3, p25) == p25 for n! and p25 = p5 // 2 since 25==5**2 . Looks like it works - jfs

225 is 9 * 25. Triplets enter factorial much more often, so you need to count fives.

Count the number of occurrences of the fives. First - multiples of 5 - their n/5 (divisions are integers). Then - multiples of 25 - n/25 . Then - 125 ... And so on, and add them all up. Since we need 25 - divide by 2. This will be the number of zeros. If, of course, we mean the number of zeros at the end of the number :)

"I think so" (c) Pooh

According to my calculations, for 1,000,000,000! the number of required zeros - 124999999.