求1*2*3*...*n结尾有多少个零的代码
时间: 2024-04-23 12:19:32 浏览: 16
求1*2*3*...*n结尾有多少个零的问题可以通过计算n的阶乘中因子5的个数来解决。因为每个因子5都会贡献一个零,所以我们只需要计算n的阶乘中有多少个因子5即可。
以下是一个示例的Python代码实现:
```python
def count_zeros(n):
count = 0
while n >= 5:
n //= 5
count += n
return count
# 示例调用
n = 10
zeros = count_zeros(n)
print(f"求1*2*3*...*{n}结尾有{zeros}个零")
```
相关问题
给出一个长度为 n的序列a,求满足如下条件连续字段的数量.令x = al * al+1 * al+2 * ... * ar.那么x的末尾恰好有k个零。再优化一下复杂度, C++代码
我们可以先将序列中的每个数分解质因数,然后对于每个区间,我们可以使用双指针来找到最短的区间使得区间内的元素的乘积末尾有 $k$ 个 $0$。
具体来说,我们可以使用一个变量 $cnt$ 记录当前区间内 $2$ 的个数,另一个变量 $cnt5$ 记录当前区间内 $5$ 的个数。然后我们移动右指针 $r$,在移动的过程中不断更新 $cnt$ 和 $cnt5$,直到 $cnt$ 和 $cnt5$ 均大于等于 $k$。此时我们可以求出当前区间的长度 $len$,那么以 $r$ 结尾的满足条件的连续子区间数量就是 $len$。
接着我们移动左指针 $l$,在移动的过程中不断更新 $cnt$ 和 $cnt5$,如果 $cnt$ 和 $cnt5$ 中有任意一个小于 $k$,我们就继续移动左指针。直到 $cnt$ 和 $cnt5$ 均大于等于 $k$,此时以 $l$ 开头的最短满足条件的区间已经找到了,以 $l$ 开头的满足条件的连续子区间数量就是 $len$。接着我们把左指针向右移动一位,再次进入右指针移动的循环。
时间复杂度为 $O(n\log w)$,其中 $w$ 是序列中的最大值。以下是 C++ 代码实现:
```c++
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 1e5;
int n, k;
int a[MAXN + 5];
vector<pair<int, int>> factors[MAXN + 5];
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
int x = a[i];
for (int j = 2; j * j <= x; j++) {
if (x % j == 0) {
int cnt = 0;
while (x % j == 0) {
cnt++;
x /= j;
}
factors[i].emplace_back(j, cnt);
}
}
if (x > 1) {
factors[i].emplace_back(x, 1);
}
}
int l = 1, r = 0;
int cnt2 = 0, cnt5 = 0;
long long ans = 0;
while (r < n) {
r++;
for (auto [p, c] : factors[r]) {
if (p == 2) {
cnt2 += c;
} else if (p == 5) {
cnt5 += c;
}
}
while (cnt2 >= k && cnt5 >= k) {
int len = r - l + 1;
ans += n - r + 1;
for (auto [p, c] : factors[l]) {
if (p == 2) {
cnt2 -= c;
} else if (p == 5) {
cnt5 -= c;
}
}
l++;
}
}
printf("%lld\n", ans);
return 0;
}
```
给出一个长度为n(1≤n≤2.105)的序列a(1≤ai≤109),并且保证序列a所有元素乘积≤1018,求这个序列中满足如下条件的连续子段[at...ar]的数量: •令x=a{:a1+1·a1+2...ar,那么x的末尾恰好有k(0≤k≤109)个零。给出c++代码
以下是代码实现:
```c++
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 5;
int n, k, ans;
int a[MAXN], cnt[MAXN], sum[MAXN];
signed main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
while (a[i] % 5 == 0) {
a[i] /= 5;
cnt[i]++;
}
}
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + cnt[i];
if (sum[i] >= k) {
ans += i - (lower_bound(sum, sum + i, sum[i] - k) - sum) + 1;
}
}
cout << ans << endl;
return 0;
}
```
思路解析:
首先我们考虑x的末尾0的个数,即x包含多少个因子5。我们可以对于每个数a[i],不断除以5,直到无法整除为止,得到a[i]中包含因子5的个数cnt[i]。这一步的时间复杂度是O(nloga),其中a为序列中元素的最大值,因为每除以一个5,a[i]的值都至少减少一个5。
接下来我们考虑如何计算连续子段的数量。我们可以维护一个前缀和数组sum,表示前i个数中包含因子5的个数之和。然后对于每个i,我们在sum[1...i]中二分查找第一个大于等于sum[i]-k的位置j,那么[j...i]就是以i为结尾、末尾有k个0的连续子段。具体地,连续子段的个数为i-j+1。
时间复杂度为O(nlogn),可以通过本题。