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

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long n, p2[200005], p5[200005];
long long c[200005];
long long a[200005], t, k;
int main() {
    cin >> t;
    while (t--) {

        cin >> n >> k;
        int cnt2 = 0, cnt5 = 0;
        p2[0] = 0;
        p5[0] = 0;
        for (int i = 1 ; i <= n ; i++) {
            cin >> a[i];
            int c2 = 0, c5 = 0;
            int t = a[i];
            while (t % 2 == 0) {
                c2++;
                t /= 2;
            }
            t = a[i];
            while (t % 5 == 0) {
                c5++;
                t /= 5;
            }
            p2[i] = p2[i - 1] + c2;
            p5[i] = p5[i - 1] + c5;

        }

        long long ans = 0;

        for (int l = 1 ; l <= n ; l++) { //枚举左界
            int l1 = l, r = n;
            while (l1 < r) { //找符合要求的下界（最小的右界）
                int mid = (l1 + r) / 2;
                long long t = min((p2[mid] - p2[l - 1]), (p5[mid] - p5[l - 1]));
                if (t >= k) r = mid ;
                else l1 = mid + 1;
            }
            long long t = min((p2[l1] - p2[l - 1]), (p5[l1] - p5[l - 1]));
            if (t != k) continue;
            int l2 = l, r2 = n;
            while (l2 < r2) { //上界
                int mid = (l2 + r2 + 1) / 2;
                long long t = min((p2[mid] - p2[l - 1]), (p5[mid] - p5[l - 1]));
                if (t > k) r2 = mid - 1 ;
                else l2 = mid;
            }
            t = min((p2[l2] - p2[l - 1]), (p5[l2] - p5[l - 1]));
            if (t != k)continue;
            ans += l2 - l1 + 1;
        }
        cout << ans << endl;
    }
    return 0;
}