SP11 FCTRL - Factorial

题目

题目链接

‍

题意

T 组数据，每组数据输入一个 N，求 Z（N）。

Z（N）是 N 的阶乘的末尾的零的个数。

N<=1e9

‍

思路

1. 根据数据范围可以判定不可以暴力求解，为规律题。

2. 打表找规律，发现

   #include 
   #define endl '\n'
   #define int long long
   using namespace std;
   const int N = 2e5 + 10;
   typedef long long ll;signed main()
   {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t;cin >> t;for (int i = 1; i <= t; i++){int ans = 1;for (int j = 1; j <= i; j++){ans = ans * j;}cout << ans << endl;}return 0;
   }

   1:1
   2:2
   3:6
   4:24
   5:120
   6:720
   7:5040
   8:40320
   9:362880
   10:3628800
   11:39916800
   12:479001600
   13:6227020800
   14:87178291200
   15:1307674368000
   16:20922789888000
   17:355687428096000
   18:6402373705728000
   19:121645100408832000
   20:2432902008176640000
   

   每 5 个数，末尾增加一个 0，但是不符合样例的输出结果。

3. 从数学角度考虑，提出问题（什么时候才会产生 0？）

4. 已知 10 = 2 * 5

5. 阶乘可以表示为 1 * 2 * 3 * 4 * 5 ··· * n

6. 2 可以用偶数来替代，数量足够多用来凑 10

7. 则需要找到阶乘中 5 的个数，5 为质因数

8. 已知 n / 5 可得 n 中有几个 5 组成（1-n 中是 5 的倍数的个数）

9. 但需要考虑有两个 5 组成的数（25 = 5 * 5）

10. 由此 题目转化为 求 n 的阶乘中 质因数 5 的个数，为答案。

‍

坑点

1. 暴力不可求解
2. 需要考虑 有两个质因数 5 的情况
3. 从数学角度分析问题

‍

算法一：思维 + 数学

‍

时间复杂度

O(N)O(N)O(N)

‍

实现步骤

1. 用 ans 累计质因数 5 的个数
2. n / 5 求 n 中 5 的个数，与 2 匹配，成为 10，作为末尾的 0
3. 累计 n / 5 的结果继续 / 5，因为其结果仍然包含质因数 5

‍

代码

#include 
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t;cin >> t;while (t--){int n;cin >> n;int ans = 0;while (1){ans += n / 5;n = n / 5;if (n < 5){break;}}cout << ans << endl;}return 0;
}

总结

数学思维好题，需要分析阶乘中末尾零由什么产生。

‍