链接:https://www.nowcoder.com/acm/contest/135/D
来源:牛客网
题目描述
输入描述:
输入数据共一行,一个正整数n,意义如“问题描述”。
输出描述:
输出一行描述答案:一个正整数k,表示S的末尾有k个0
<!–
–>
输入例子:
10
输出例子:
7
–>
示例1
输入
10
输出
7
说明
鸣谢真·dalao Tyxao 计算阶乘末尾零的个数是计算中间包含多少个5的个数所以我们直接暴力枚举每个数的阶乘的5的个数,因为接下来的数里都包含这个数的阶乘,所以还要乘以个剩余的个数
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define debug(a) cout << #a << " " << a << endl
using namespace std;
const int maxn = 1e8;
const int mod = 1e9 + 7;
typedef long long ll;
int main() {
std::ios::sync_with_stdio(false);
ll n, sum = 0;
cin >> n;
for( ll i = 1; i <= n; i ++ ) {
ll j = i, cnt = 0;
while( j%5 == 0 ) {
cnt ++;
j /= 5;
}
sum += cnt*(n-i+1);
}
cout << sum << endl;
return 0;
}
看别人的代码有直接推出公式的
平常的时候,是每隔5个差值加一,当相乘的数多了一个5的时候差值会再多加一个一
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define debug(a) cout << #a << " " << a << endl
using namespace std;
const int maxn = 1e8;
const int mod = 1e9 + 7;
typedef long long ll;
int main() {
std::ios::sync_with_stdio(false);
ll n, m = 5, sum = 0;
cin >> n;
if( n < 5 ) {
cout << sum << endl;
} else {
while( m < n ) {
sum += ((n+1-m)+(1+n%m))*(n/m)/2;
m *= 5;
}
cout << sum << endl;
}
return 0;
}