题解 | #Kevin喜欢零(困难版本)#

1. 差分转化

直接统计“恰好等于 $k$ ”较为困难，因为 $\min(V_2, V_5) = k$ 是一个非单调的约束。依据排除法原理，我们可以将约束转化为： $\text{Count}(\min \ge k) - \text{Count}(\min \ge k+1)$ 令 $f(K)$ 为满足 $\min(V_2(l, r), V_5(l, r)) \ge K$ 的子段数量。条件 $\min(V_2, V_5) \ge K$ 等价于： $V_2(l, r) \ge K \quad \text{AND} \quad V_5(l, r) \ge K$ 这是一个具有二元单调性的判定问题，非常适合双指针或滑动窗口优化。

2. 双指针 + 滑动窗口

对于确定的左端点 $l$ ，随着右端点 $r$ 的增加， $V_2$ 和 $V_5$ 同步增加。

如果我们找到了最小的 $r_{min}$ 使得 $V_2(l, r_{min}) \ge K$ 且 $V_5(l, r_{min}) \ge K$ ，那么对于所有 $r \in [r_{min}, n]$ ，该条件均成立。
此时，以 $l$ 为左端点且满足条件的子段数量为 $n - r_{min} + 1$ 。
利用双指针，左端点 $l$ 主动右移，右端点 $r$ 根据条件联动右移，复杂度可控制在 $O(n)$ 。

3. 复杂度分析

时间复杂度：
- 因子提取：对于每个元素 $a_i$ ，通过循环除法提取因子，复杂度为 $O(n \log (\max a_i))$ 。
- 双指针扫描：计算 $f(k)$ 和 $f(k+1)$ 分别需要一次线性扫描，复杂度为 $O(n)$ 。
- 总体： $O(T \cdot n \cdot \log(\max a_i))$ 。
空间复杂度：
- 需要存储每个元素的 $v_2$ 和 $v_5$ 计数，空间复杂度为 $O(n)$ 。

4. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    auto decomposition = [](int factor, ll v, vector<ll>& cnt,
    int idx) -> void {
        ll c = 0;
        while (v % factor == 0) {
            c++;
            v /= factor;
        }
        cnt[idx] = c;
    };

    int T;
    cin >> T;

    while (T--) {
        int n;
        ll k;
        cin >> n >> k;

        vector<ll> cnt2(n), cnt5(n);
        for (int i = 0; i < n; i++) {
            ll a;
            cin >> a;
            decomposition(2, a, cnt2, i);
            decomposition(5, a, cnt5, i);
        }

        auto count_at_least = [&](ll k) -> ll {
            if (k == 0) {
                return (ll)n * (n + 1) / 2;
            }

            ll res = 0;
            int r = 0;
            ll sum2 = 0;
            ll sum5 = 0;

            for (int l = 0; l < n; l++) {
                while (r < n && (sum2 < k || sum5 < k)) {
                    sum2 += cnt2[r];
                    sum5 += cnt5[r];
                    r++;
                }
                if (sum2 >= k && sum5 >= k) {
                    res += (n - r + 1);
                }
                sum2 -= cnt2[l];
                sum5 -= cnt5[l];
            }

            return res;
        };

        ll ans = count_at_least(k) - count_at_least(k + 1);
        cout << ans << "\n";
    }
}