解题思路
一个整数末尾有多少个连续零，取决于它含有多少个因子 10。
而
10=2×5
所以一个子数组乘积末尾连续零的个数，等于这个子数组乘积中因子 2 的总个数与因子 5 的总个数的较小值，即：
zero(l,r)=min(i=l∑rv2(ai),i=l∑rv5(ai))
其中：
- v2(x) 表示 x 中因子 2 的个数
- v5(x) 表示 x 中因子 5 的个数
题目要求统计满足：
min(∑v2,∑v5)≥k
的子数组个数。
这等价于同时满足：
∑v2≥k且∑v5≥k
因此，问题转化为：
给定两个非负数组：
- bi=v2(ai)
- ci=v5(ai)
统计有多少个子数组 [l,r] 满足：
i=l∑rbi≥k且i=l∑rci≥k
具体算法
这里使用 双指针（滑动窗口） 来解决。
先对每个 ai 分解出其中因子 2 和因子 5 的个数。
然后维护一个窗口 [l,r]，并记录窗口内：
- 因子 2 的总数
sum2
- 因子 5 的总数
sum5
对于每一个左端点 l：
-
不断右移右端点 r，直到窗口内满足：
sum2≥k且sum5≥k
或者 r 已经到达数组末尾。
-
如果当前窗口已经满足条件，那么以当前 l 为左端点，所有右端点在 r,r+1,…,n−1 的子数组都满足条件。
因为每个元素贡献的因子个数都非负，窗口继续向右扩展时，sum2 和 sum5 只会更大，不会变小。
所以这一轮贡献为：
n−r
-
然后左端点右移，即把 al 对应的因子贡献从窗口中减去，继续处理下一个左端点。
实现细节
对于每个数 ai：
- 不断除以 2，统计因子 2 的个数
- 不断除以 5，统计因子 5 的个数
由于 ai≤109，所以每个数最多被除几十次，代价很小。
最终答案可能很大，最多可达：
2n(n+1)
因此需要使用 long long / long / Python 整数来保存答案。
复杂度分析
设数组长度为 n。
时间复杂度
- 预处理每个数的因子 2 和因子 5 个数：总复杂度为 O(nlogai)，但由于只除以 2 和 5，实际每个数最多循环几十次，可视为 O(n)
- 双指针过程中，左右指针都只会从左到右各移动一次，总复杂度为 O(n)
因此总时间复杂度为：
O(n)
空间复杂度
如果把每个元素的因子个数预处理到数组中，需要额外空间：
O(n)
因此空间复杂度为：
O(n)
该复杂度对于 n≤2×105 是完全可行的。
代码实现
import sys
# 统计一个正整数中因子 2 和因子 5 的个数
def get_factor_count(x):
cnt2 = 0
cnt5 = 0
# 统计因子 2 的个数
while x % 2 == 0:
cnt2 += 1
x //= 2
# 统计因子 5 的个数
while x % 5 == 0:
cnt5 += 1
x //= 5
return cnt2, cnt5
# 统计满足条件的子数组个数
def count_divisible_subarrays(n, k, arr):
twos = [0] * n
fives = [0] * n
# 预处理每个元素中因子 2 和因子 5 的个数
for i in range(n):
twos[i], fives[i] = get_factor_count(arr[i])
ans = 0
sum2 = 0
sum5 = 0
r = 0
# 枚举左端点
for l in range(n):
# 扩展右端点，直到当前窗口满足条件
while r < n and (sum2 < k or sum5 < k):
sum2 += twos[r]
sum5 += fives[r]
r += 1
# 如果当前窗口满足条件
# 此时窗口是 [l, r-1]
# 那么右端点取 r-1 到 n-1 都合法
if sum2 >= k and sum5 >= k:
ans += n - r + 1
# 左端点右移前，移除当前左端点的贡献
sum2 -= twos[l]
sum5 -= fives[l]
return ans
def main():
data = list(map(int, sys.stdin.read().split()))
n, k = data[0], data[1]
arr = data[2:2 + n]
print(count_divisible_subarrays(n, k, arr))
if __name__ == "__main__":
main()
#include <iostream>
#include <vector>
using namespace std;
// 统计一个正整数中因子 2 和因子 5 的个数
pair<int, int> getFactorCount(int x) {
int cnt2 = 0;
int cnt5 = 0;
// 统计因子 2 的个数
while (x % 2 == 0) {
cnt2++;
x /= 2;
}
// 统计因子 5 的个数
while (x % 5 == 0) {
cnt5++;
x /= 5;
}
return {cnt2, cnt5};
}
// 统计满足条件的子数组个数
long long countDivisibleSubarrays(int n, long long k, const vector<int>& arr) {
vector<int> twos(n), fives(n);
// 预处理每个元素中因子 2 和因子 5 的个数
for (int i = 0; i < n; i++) {
pair<int, int> res = getFactorCount(arr[i]);
twos[i] = res.first;
fives[i] = res.second;
}
long long ans = 0;
long long sum2 = 0;
long long sum5 = 0;
int r = 0;
// 枚举左端点
for (int l = 0; l < n; l++) {
// 扩展右端点，直到当前窗口满足条件
while (r < n && (sum2 < k || sum5 < k)) {
sum2 += twos[r];
sum5 += fives[r];
r++;
}
// 如果当前窗口满足条件
// 此时窗口是 [l, r-1]
// 那么右端点从 r-1 到 n-1 都满足条件
if (sum2 >= k && sum5 >= k) {
ans += n - r + 1;
}
// 左端点右移前，移除当前左端点的贡献
sum2 -= twos[l];
sum5 -= fives[l];
}
return ans;
}
int main() {
int n;
long long k;
cin >> n >> k;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << countDivisibleSubarrays(n, k, arr) << '\n';
return 0;
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
// 统计一个正整数中因子 2 和因子 5 的个数
public static int[] getFactorCount(int x) {
int cnt2 = 0;
int cnt5 = 0;
// 统计因子 2 的个数
while (x % 2 == 0) {
cnt2++;
x /= 2;
}
// 统计因子 5 的个数
while (x % 5 == 0) {
cnt5++;
x /= 5;
}
return new int[]{cnt2, cnt5};
}
// 统计满足条件的子数组个数
public static long countDivisibleSubarrays(int n, long k, int[] arr) {
int[] twos = new int[n];
int[] fives = new int[n];
// 预处理每个元素中因子 2 和因子 5 的个数
for (int i = 0; i < n; i++) {
int[] res = getFactorCount(arr[i]);
twos[i] = res[0];
fives[i] = res[1];
}
long ans = 0;
long sum2 = 0;
long sum5 = 0;
int r = 0;
// 枚举左端点
for (int l = 0; l < n; l++) {
// 扩展右端点，直到当前窗口满足条件
while (r < n && (sum2 < k || sum5 < k)) {
sum2 += twos[r];
sum5 += fives[r];
r++;
}
// 如果当前窗口满足条件
// 此时窗口为 [l, r-1]
// 那么右端点从 r-1 到 n-1 都满足条件
if (sum2 >= k && sum5 >= k) {
ans += n - r + 1;
}
// 左端点右移前，移除当前左端点的贡献
sum2 -= twos[l];
sum5 -= fives[l];
}
return ans;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
long k = Long.parseLong(st.nextToken());
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
System.out.println(countDivisibleSubarrays(n, k, arr));
}
}
