題目

  • Time limit: 1.00 s
  • Memory limit: 512 MB

Your task is to calculate the number of trailing zeros in the factorial n!.
For example, 20!=243290200817664000020!=2432902008176640000 and it has 44 trailing zeros.

Input Output
The only input line has an integer nn. Print the number of trailing zeros in n!n!.

Constraints

  • 1≤n≤1091 \le n \le 10^9

Example:

Input Output
20 4

解法

分析

這題十分經典，是要求n!n!尾部有幾個00。
注意到n!n!尾部00的個數==滿足10k∣n!10^k | n!的kk的最大值(也就是n!n!能被1010整除幾次)=n!=n!的質因數分解中55的次方數(因為10=2⋅510=2\cdot 5，而又顯然n!n!的質因數分解中55的次數會比22來的少)

接著，n!n!的質因數分解中55的次數即為11~nn中每個數個別被55整除的次數之和。
11~nn中，

  • 被55整除的數有⌊n5⌋\lfloor\frac{n}{5}\rfloor個
  • 被525^2整除的數有⌊n52⌋\lfloor\frac{n}{5^2}\rfloor個
  • 被535^3整除的數有⌊n53⌋\lfloor\frac{n}{5^3}\rfloor個
    等等，於是所求即

⌊n5⌋+⌊n52⌋+⌊n53⌋+⋯=∑k=1∞⌊n5k⌋\lfloor\frac{n}{5}\rfloor+\lfloor\frac{n}{5^2}\rfloor+\lfloor\frac{n}{5^3}\rfloor+\cdots=\sum\limits_{k=1}^\infty\lfloor\frac{n}{5^k}\rfloor

此即勒讓德定理(Legendre’s Theorem)：

νp(n!)=∑k=1∞⌊npk⌋\nu_{p}(n!)=\sum\limits_{k=1}^\infty\lfloor\frac{n}{p^k}\rfloor

其中νp(x)\nu_p(x)表示滿足pk∣xp^k|x的最大正整數kk(即xx被pp整除幾次)

在計算時，我們可以用以下性質簡化計算：

⌊xab⌋=⌊⌊xa⌋b⌋\lfloor \frac{x}{ab} \rfloor=\lfloor \frac{\lfloor \frac{x}{a}\rfloor}{b} \rfloor

AC Code

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  int z = n, ans = 0;
  while(z != 0){
    z /= 5;
    ans += z;
  }
  cout << ans;
}

很簡單吧~