我之前的想法是，只有到 5 的时候才多一个零。不过经同学指正是不对的。感谢！
这里数阶乘 $n!$ 右侧的零，注意到 $n! = a * 10^b$，其中 a 是 $n!$ 去掉右侧 0 的部分。这说明 $n!$ 可以分解出 n 个 10 相乘。又因为只有 2 和 5 两个质数相乘才能得到 10，所以原问题等价于求 $n!$ 可以分解出多少个 2 或 5，取其中较小的为答案（多余的 2 或 5 不能拼出 10）。
因为 $n!$ 质因数分解后，2 出现的次数恒大于等于 5 出现的次数，所以只需要求 $n!$ 质因数分解后有多少个 5，这就是答案。因为阶乘数可能很大，求出它的值不现实，所以我们必须寻找其它方法。幸运的是，我们不需要得到 $n!$ 的值而只需要它所有的因数里 5 的个数。
此外，由于阶乘的特性，如果定义 $f(n)$ 为 $n!$ 右侧零的个数，$g(x)$ 为 $x$ 的质因数中 5 的个数，那么满足 $$ f(n）= \begin{cases} 0 & n < 5 \ f(n-1) + g(n) & n \ge 5 \end{cases} $$
根据这个式子可以方便地推出从 $n \in [1, 25]$ 的所有对应答案，只需要打一张表。下面是按上述思路结论直接写出的代码：
#include <iostream> int g(int n) { int ret = 0; while (n % 5 == 0) { n /= 5; ++ret; } return ret; } int f(int n) { if (n < 5) return 0; else return f(n - 1) + g(n); } int main() { int t; scanf("%d", &t); for (int i = 0; i < t; ++i) { int n; scanf("%d", &n); printf("case #%d:\n%d\n", i, f(n)); } }
打表也很简单，下面是表：
f(0) = 0 f(1) = 0 f(2) = 0 f(3) = 0 f(4) = 0 f(5) = 1 f(6) = 1 f(7) = 1 f(8) = 1 f(9) = 1 f(10) = 2 f(11) = 2 f(12) = 2 f(13) = 2 f(14) = 3 f(15) = 3 f(16) = 3 f(17) = 3 f(18) = 3 f(19) = 3 f(20) = 4 f(21) = 4 f(22) = 4 f(23) = 4 f(24) = 4 f(25) = 6 f(26) = 6 f(27) = 6 f(28) = 6 f(29) = 7 f(30) = 7 f(31) = 7 f(32) = 7 f(33) = 7 f(34) = 7 f(35) = 8 f(36) = 8 f(37) = 8 f(38) = 8 f(39) = 8 f(40) = 9 f(41) = 9 f(42) = 9 f(43) = 9 f(44) = 10 f(45) = 10 f(46) = 10 f(47) = 10 f(48) = 10 f(49) = 10 f(50) = 12
来了兴趣，用 Rust 写一下上面的代码，其实也没有什么花样。
fn g(mut x: u32) -> u32 { let mut ret = 0; while x % 5 == 0 { x /= 5; ret += 1; } ret } fn f(n: u32) -> u32 { if n < 5 { 0 } else { f(n - 1) + g(n) } }
居然是最右端的零的个数，不是等号右端零的个数QAQ
using namespace std;
int main() { int n; cin >> n; int i; for(i = 0; i < n; i++){ int num; int cnt; cin >> num; if(num >= 1 && num < 5){ cnt = 0; } if(num >= 5 && num < 10){ cnt = 1; } if(num >= 10 && num < 15){ cnt = 2; } if(num >= 15 && num < 20){ cnt = 3; } if(num == 20){ cnt = 4; } cout << “case #” << i << “:” << endl; cout << cnt << endl; } return 0; }
void FactorialZeros(int n){ int b; b=n/5; printf(“%d\n”,b); } int main() { int N,n; scanf(“%d”,&N); int i; int a[N]; for(i=0;i<N;i++){ scanf(“%d”,&a[i]);} for(i=0;i<N;i++){ printf(“case #%d:\n”,i); FactorialZeros(a[i]);} }
归纳可知只有到5 的时候才会多一个零。
#include <cstdio> inline unsigned get_uint() { unsigned ans = 0; char ch = getchar(); while (ch < '0' || '9' < ch) ch = getchar(); while ('0' <= ch && ch <= '9') { ans = ans * 10 + ch - '0'; ch = getchar(); } return ans; } int main() { unsigned n = get_uint(); for (int i = 0; i < n; ++i) printf("case #%i:\n%i\n", i, get_uint() / 5); }
我之前的想法是，只有到 5 的时候才多一个零。不过经同学指正是不对的。感谢！
这里数阶乘 $n!$ 右侧的零，注意到 $n! = a * 10^b$，其中 a 是 $n!$ 去掉右侧 0 的部分。这说明 $n!$ 可以分解出 n 个 10 相乘。又因为只有 2 和 5 两个质数相乘才能得到 10，所以原问题等价于求 $n!$ 可以分解出多少个 2 或 5，取其中较小的为答案（多余的 2 或 5 不能拼出 10）。
因为 $n!$ 质因数分解后，2 出现的次数恒大于等于 5 出现的次数，所以只需要求 $n!$ 质因数分解后有多少个 5，这就是答案。因为阶乘数可能很大，求出它的值不现实，所以我们必须寻找其它方法。幸运的是，我们不需要得到 $n!$ 的值而只需要它所有的因数里 5 的个数。
此外，由于阶乘的特性，如果定义 $f(n)$ 为 $n!$ 右侧零的个数，$g(x)$ 为 $x$ 的质因数中 5 的个数，那么满足
$$
f(n）= \begin{cases}
0 & n < 5 \
f(n-1) + g(n) & n \ge 5
\end{cases}
$$
根据这个式子可以方便地推出从 $n \in [1, 25]$ 的所有对应答案，只需要打一张表。下面是按上述思路结论直接写出的代码：
打表也很简单，下面是表：
来了兴趣，用 Rust 写一下上面的代码，其实也没有什么花样。
居然是最右端的零的个数，不是等号右端零的个数QAQ
include
include
using namespace std;
int main()
{
int n;
cin >> n;
int i;
for(i = 0; i < n; i++){
int num;
int cnt;
cin >> num;
if(num >= 1 && num < 5){
cnt = 0;
}
if(num >= 5 && num < 10){
cnt = 1;
}
if(num >= 10 && num < 15){
cnt = 2;
}
if(num >= 15 && num < 20){
cnt = 3;
}
if(num == 20){
cnt = 4;
}
cout << “case #” << i << “:” << endl;
cout << cnt << endl;
}
return 0;
}
include
include
void FactorialZeros(int n){
int b;
b=n/5;
printf(“%d\n”,b);
}
int main()
{
int N,n;
scanf(“%d”,&N);
int i;
int a[N];
for(i=0;i<N;i++){
scanf(“%d”,&a[i]);}
for(i=0;i<N;i++){
printf(“case #%d:\n”,i);
FactorialZeros(a[i]);}
}
归纳可知只有到5 的时候才会多一个零。