今天也是参加了一下宁波大学的校赛,其中有一道题是求后缀0的个数,题意是让我们求一下式子的后缀0个数:
看上去比较复杂,但是通过化简我们可以知道以上式子就是求(n + 1)!,这里化简的过程就不展示了,比较基础。那么我们如何高效地求出后缀0的个数呢?
我们知道,后缀0其实是由一个一个10乘上去的,所以我们需要搞清楚10是怎么来的,我们知道,像10,20,30这些已经很明确告诉我们有10的存在,那么还有呢?没错,就是5*偶数,因为我们的偶数是每两个数出现一次的,他的出现频率非常高,所以我们其实只需要找到5的个数就可以了,所以问题就十分简单了,我们将阶乘底数除五除尽不就是五出现的次数了吗,所以总体代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
ULL T, n, ans;
int main()
{
cin >> T;
while(T --)
{
ans = 0;
cin >> n;
n += 1;
while(n)
ans += n /= 5;
cout << ans << endl;
}
}
这些数学内容相对比较基础,只要能够记住原理就可以非常熟练的用出来,但好像比赛上没什么用,毕竟太偏了,而且体型比较单一。