给出一个长度为 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++ 代码实现：

#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;
}