小美的区间删除

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int k = in.nextInt();
        int[]nums = new int[n];
        in.nextLine();
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        long res=sectionDel(nums,k);
        System.out.println(res);
    }

    /*
    思路 :  滑动窗口
    因为 元素 都大于 1  所以 所有的 0  只能来自 与 2  5 两个因子
    例如  25 6  15 4  等 即5 的倍数 或者 2 的倍数  二者相乘 才能多出1个 零
    或者 本身既是2的倍数 又是 五的倍数 那就是 本身就 携带零的;
     */
    public static long sectionDel(int[]nums, int k) {
        // i 位置包含 几个 2 这个因子  // 例如20  20/2=10  10/2=5  也就是包含两个 2
        int[] countBy2 = new int[nums.length];
        //同理 nums[i] 包含几个 5 这个因子
        int[] countBy5 = new int[nums.length];
        // 2 和 5  因子 的总数
        int total2 = 0;
        int total5 = 0;

        for (int i = 0; i < nums.length; i++) {
            while (nums[i] % 2 == 0) {
                nums[i] /= 2;
                countBy2[i]++;
                total2++;
            }
            while (nums[i] % 5 == 0) {
                nums[i] /= 5;
                countBy5[i]++;
                total5++;
            }
        }
        // 滑动窗口计算 可以有多少个可删除的   连续 子序列 注意是连续 ,不能跳着删的
        int l = 0;
        long res = 0;
        /* 滑动窗口统计的是可以删除的 区间 有几个
         依旧 有 dp的思想在 例如 只有一个 元素 的区间
         1  可删除的数字就一个
         1 2  可删除的 区间 1 , 2  , 1 2  三个
         1 2 3 可删除区间   1 ,2 ,1 2, 3 ,2 3,1 2 3  六个
           就可以发现规律 了 从后向前 看  例如 多出一个3 的时候  可删除的区间
             多了  3 ,2 3,1 2 3  这三个 再加上 只有 1 2 两个数字时可组成的区间
             这样 从前向后推导
             dp[i]  含义  共 i个数 可组成的连续子序列共 dp[i]个
             dp[1]=1  dp[i]=dp[i-1]+i
         */
        for (int r = 0; r < nums.length; r++) {
            total2 -= countBy2[r];
            total5 -= countBy5[r];
            // 可以删除的区间统计个数 ,如果遇到 不能删的 元素(注意是元素)
            //就调整 l 的位置 向后移动,(r的每次右移 都在尝试 寻找连续可删 区间的长度)
            while (Math.min(total2, total5) < k && l <= r) {
                //把途中的 2 或者 5 补充回来 ,直到满足要求
                total2 += countBy2[l];
                total5 += countBy5[l];
                l++;
            }
            // 之所以是 r-l+1 原因就类似于 使用 dp[i];
            res += r - l + 1;
        }
        return res;
    }
}

看了好几篇评论区中的答案，然后按照自己想法重新写了一遍。

重点，元素均大于0，所以0的生成仅和因子2和5的个数有关，即0的个数为

所以，需要知道任意区间中2和5的个数，刚好前缀和可以做到。prefix2[i]表示[0,i)区间2的个数,同理prefix5[i]表示[0,i)区间5的个数,那么任意区间2因子[left,right),（注意，区间是左闭右开）的个数则为sum = prefix2[right]-prefix2[left],求5因子同理。

最后，我们使用滑动窗口枚举右端点即可，将每个可删除区间的长度作为答案加入res中。

C++代码如下:

#include <iostream>
using namespace std;
#include <vector>

//求解X中包含base因子的个数
int factor(int x, int base) {
    int cnt = 0;
    while (x && (x % base == 0)) {
        ++cnt;
        x /= base;
    }
    return cnt;
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    vector<int> nums(n);
    vector<int> factor2(n + 1);
    vector<int> factor5(n + 1);

    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        factor2[i + 1] = factor2[i] + factor(nums[i], 2);
        factor5[i + 1] = factor5[i] + factor(nums[i], 5);
    }

    long long res = 0;

    //使用滑动窗口
    int right = 0;
    int left = 0;
    int total2;
    int total5;
    while (right < n) { //可删除区间[left,right)
        ++right;
        total2 = factor2[n] + factor2[left] - factor2[right];
        total5 = factor5[n] + factor5[left] - factor5[right];
        while (left < right && min(total2, total5) < k) {
            ++left;
            total2 = factor2[n] + factor2[left] - factor2[right];
            total5 = factor5[n] + factor5[left] - factor5[right];
        }
        // cout << left << " : " << right << endl;
        res += right - left;
    }

    cout << res << endl;

    return 0;
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt(), k = in.nextInt();
            int[] a = new int[n];
            for(int i = 0;i < n;i++){
                a[i] = in.nextInt();
            }
            int[] countBy2 = new int[n], countBy5 = new int[n];
            for(int i = 0;i < n;i++){
                while(a[i] % 2 == 0){
                    a[i] /= 2;
                    countBy2[i]++;
                }
                while(a[i] % 5 == 0){
                    a[i] /= 5;
                    countBy5[i]++;
                }
            }
            int totalBy2 = 0, totalBy5 = 0;
            for(int i = 0;i < n;i++){
                totalBy2 += countBy2[i];
                totalBy5 += countBy5[i];
            }
            long res = 0;
            for(int i = 0, j = 0;j < n;j++){
                totalBy2 -= countBy2[j];
                totalBy5 -= countBy5[j];
                while(i <= j && Math.min(totalBy2, totalBy5) < k){
                    totalBy2 += countBy2[i];
                    totalBy5 += countBy5[i];
                    i++;
                }
                res += j - i + 1;
            }
            System.out.println(res);
        }
    }
}

n, k = map(int, input().split())
li = list(map(int, input().split()))
numli = []

for x in li:
    t = x
    a = b = 0
    while t % 2 == 0&nbs***bsp;t % 5 == 0:
        if t % 2 == 0:
            t //= 2
            a += 1
        if t % 5 == 0:
            b += 1
            t //= 5
    numli.append((a, b))
# print(numli)
sm2 = [0] * (n + 1) # 求2的数量的前缀和
sm5 = [0] * (n + 1)
for i in range(1, n + 1):
    sm2[i] = sm2[i - 1] + numli[i - 1][0]
    sm5[i] = sm5[i - 1] + numli[i - 1][1]

# print(sm2)
# print(sm5)

i= 0
j = 0
res = 0
while i < n + 1:
    while j < n + 1:
        a2 = sm2[-1] - sm2[j] + sm2[i]
        a5 = sm5[-1] - sm5[j] + sm5[i]
        if min(a2, a5) < k:
            break
        j += 1
    if i >= j:
        break
    res += j - 1 - i
    i += 1
print(res)
    

    

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int factor(int n, int base){
    int ans = 0;
    while (n and !(n%base)) {
        n/=base;
        ans++;
    }
    return ans;
}

int base_right(const vector<int>& vec, int value){
    int left = 0;
    int right = vec.size()-1;
    int res = -1;
    while (left<=right) {
        int mid = left+((right-left)>>1);
        if(vec[mid]>value){
            res  = mid;
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    if(res == -1) return vec.size();
    return res;
}

int main() {
    int n, k;
    cin>>n>>k;

    vector<int> vec(n);
    vector<int> factor2(n+1);
    vector<int> factor5(n+1);

    int totle2 = 0;
    int totle5 = 0;
    for(int i=0;i<n;i++){
        cin>>vec[i];
        int x = factor(vec[i], 2);
        factor2[i+1] = factor2[i]+x;
        totle2+=x;
        x = factor(vec[i], 5);
        factor5[i+1] = factor5[i]+x;
        totle5+=x;
    }
    // 这里进行二分查找加速
    long long ans = 0;
    for(int i=0;i<n;i++){ // 以每个点为起点
        int val2 = totle2+factor2[i]-k;
        int val5 = totle5+factor5[i]-k;
        int pos2 = base_right(factor2, val2);
        int pos5 = base_right(factor5, val5);
        if(min(pos2, pos5)-i-1<=0) continue;
        ans+=min(pos2, pos5)-i-1;
    }
    cout<<ans<<endl;
    return 0;
}

Java版 前序和+二分

自然的想法是找出数组中，每个元素2和5因数的个数，然后判断删除后min(剩余元素2的因数和,5的因数)是否大于等于k即可。

1. 二分查找区间遍历：正常来说，需要o(n^2)的复杂度来遍历每个区间。通过二分查找，可以将复杂度下降到o(nlogn)。
2. 由于是找因数和，用前序和可以减少重复累加因数和，同时将数组转变成了有序数组，使二分查找成为可能。

二分查找的思路：
mid是前序和中需要保留的元素，所以会加上这一部分的因数。最后要让mid的值为满足因数和要求的最小值。

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 注意 hasNext 和 hasNextLine 的区别
        String[] str =br.readLine().split(" ");
        int n = Integer.valueOf(str[0]);
        int k = Integer.valueOf(str[1]);
        String[] arr =br.readLine().split(" ");
        Long[] five = new Long[n];
        Long[] two = new Long[n];
        Long[] fivePre = new Long[n+1];
        Long[] twoPre = new Long[n+1];
        fivePre[0]=0L;
        twoPre[0]=0L;
        for(int i=0; i< five.length; i++){
            five[i] = divide(Long.valueOf(arr[i]), 5);
            fivePre[i+1]= five[i]+fivePre[i];
            two[i] = divide(Long.valueOf(arr[i]), 2);
            twoPre[i+1]=two[i]+twoPre[i];
        }
        Long result =0L;

        for(int a=1; a<=five.length; a++){
            result += binarySearch(a, k, fivePre, twoPre, n);
        }
        br.close();
        try(BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))){
            bw.write(result+" ");
            bw.newLine();
            bw.flush();
        }

    }
    public static Long divide(Long summ, int n){
        Long result =0L;
        while(summ%n==0){
            summ = summ/n;
            result++;
        }
        return result;
    }
    public static int binarySearch(int a, int target, Long[] fivePre, Long[] twoPre, int len){
        int pre = 0;
        int last = a;
        Long sumFive = fivePre[len];
        Long sumTwo = twoPre[len];
        int mid =0;
        while(pre<last){
            mid = (pre+last)/2;
            Long calFive = sumFive - fivePre[a]+ fivePre[mid];
            Long calTwo = sumTwo - twoPre[a] + twoPre[mid];
            if(Math.min(calFive,calTwo)>=target){
                last=mid;
            }
            else if(Math.min(calFive,calTwo)<target){
                pre=mid+1;
            }
        }
        mid = (pre+last)/2;
        return a-mid;
    }
}

import sys

def count_factor(num, factor):
    cnt = 0
    while num % factor == 0:
        cnt += 1
        num = num // factor
    return cnt

def main():
    n, k = map(int, sys.stdin.readline().split())
    arr = list(map(int, sys.stdin.readline().split()))
    
    two = []
    five = []
    for num in arr:
        two.append(count_factor(num, 2))
        five.append(count_factor(num, 5))
    
    pre_two = [0] * (n + 1)
    pre_five = [0] * (n + 1)
    for i in range(n):
        pre_two[i + 1] = pre_two[i] + two[i]
        pre_five[i + 1] = pre_five[i] + five[i]
    
    sum2 = pre_two[n]
    sum5 = pre_five[n]
    
    target2 = sum2 - k
    target5 = sum5 - k
    
    if target2 < 0&nbs***bsp;target5 < 0:
        print(0)
        return
    
    res = 0
    l = 0
    for r in range(1, n + 1):
        while l < r and (pre_two[r] - pre_two[l] > target2&nbs***bsp;pre_five[r] - pre_five[l] > target5):
            l += 1
        res += r - l
    
    print(res)

if __name__ == "__main__":
    main()

0数量=2因子数和5因子数的最小值。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        int s2[] = new int[n+1], s5[] = new int[n+1];
        for(int i=1;i<=n;++i) {
            int a = in.nextInt();
            while(a%2==0) {
                ++s2[i];
                a/=2;
            }
            while(a%5==0) {
                ++s5[i];
                a/=5;
            }
            //System.out.println(s2[i]+" "+s5[i]);
            s2[i]+=s2[i-1];
            s5[i]+=s5[i-1];
        }
        //System.out.println(s2[n]+" "+s5[n]);
        long ans=0;
        for(int r=1;r<=n;++r) {
            int lf=1, rf=r, l=r+1;
            while(lf<=rf) {
                int cf=(lf+rf)>>1;
                int m2 = s2[r] - s2[cf-1];
                int m5 = s5[r] - s5[cf-1];
                //System.out.println(cf+" "+r+" "+m2+" "+m5);
                int n0 = Math.min(s2[n]-m2, s5[n]-m5);
                if(n0>=k) {
                    l=cf;
                    rf=cf-1;
                }else{
                    lf=cf+1;
                }
            }
            //System.out.println(l+" "+r);
            ans+=Math.max(0, r-l+1);
        }
        System.out.println(ans);
    }
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        int n2[] = new int[n], n5[] = new int[n];
        int s2=0,s5=0;
        for(int i=0;i<n;++i) {
            int a = in.nextInt();
            while(a%2==0) {
                ++n2[i];
                a/=2;
            }
            while(a%5==0) {
                ++n5[i];
                a/=5;
            }
            s2+=n2[i];
            s5+=n5[i];
        }
        long ans=0;
        int c2=0,c5=0;
        for(int r=0,l=0;r<n;++r) {
            c2+=n2[r];
            c5+=n5[r];
            while(l<=r&&Math.min(s5-c5,s2-c2)<k) {
                c2-=n2[l];
                c5-=n5[l];
                l+=1;
            }
            ans+=Math.max(0,r-l+1);
        }
        System.out.println(ans);
    }
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int>sum_2(n+1);
    vector<int>sum_5(n+1);
    for(int i = 1; i <= n; i++){
        int _num;
        int tmp;
        cin >> _num; 
        tmp = _num;
        sum_2[i] += sum_2[i-1];
        sum_5[i] += sum_5[i-1];
        while(tmp >= 2){
            if(tmp % 2==0){        //位操作更快一点if(!(tmp & 1)){tmp >> 1;sum_2[i] += 1;}更快一点
                sum_2[i] += 1;
                tmp /= 2;
            }else{
                break;
            }
        }
        tmp = _num;
        while(tmp >= 5){
            if(tmp % 5==0){
                sum_5[i] += 1;
                tmp /= 5;
            }else{
                break;
            }
        }
    }
    long ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            int num_2 = sum_2[n] - sum_2[i] + sum_2[j-1];
            int num_5 = sum_5[n] - sum_5[i] + sum_5[j-1];
            int num_0 = min(num_2, num_5);
            if(num_0 >= k){
                ans += i - j + 1;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
} 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        int sum2 = 0;
        int sum5 = 0;
        for (int i = 0; i < n; i++) {
            int x = in.nextInt();
            int y = x;
            while (x % 2 == 0) {
                a[i] ++;
                x /= 2;
            }
            sum2 += a[i];
            while (y % 5 == 0) {
                b[i] ++;
                y /= 5;
            }
            sum5 += b[i];
        }
        if (Math.min(sum2, sum5) < k) System.out.println(0);
        else {
            int k2 = sum2 - k;
            int k5 = sum5 - k;
            int x = 0;
            int y = 0;
            long ans = 0;
            int l = 0;
            for (int i = 0; i < n; i++) {
                x += a[i];
                y += b[i];
                while (x > k2 || y > k5) {
                    x -= a[l];
                    y -= b[l++];
                }
                ans += 1l * (i - l + 1);
            }
            System.out.println(ans);
        }
    }
}

#include <iostream>
#include <vector>
using namespace std;

class sol {
  public:
    sol(int n): N(n), nums(n) {}
    void add(int i, int x) {
        nums[i].first = x;
        int a = 0, b = 0;
        while (!(x % 2)) {
            ++a;
            x /= 2;
        }
        c2 += (nums[i].second.first = a);
        while (!(x % 5)) {
            ++b;
            x /= 5;
        }
        c5 += (nums[i].second.second = b);
    }
    long long get(int k) {
        c2 -= k, c5 -= k;
        if (c2 < 0 || c5 < 0)return 0;
        cnt = 0;
        getmain();
        c2 += k, c5 += k;
        return cnt;
    }
    long long getmain() {
        int i = 0, j = 0;
        while (j < N) {
            c2 -= nums[j].second.first;
            c5 -= nums[j].second.second;
            ++j;

            while (i < j && (c2 < 0 || c5 < 0)) {
                c2 += nums[i].second.first;
                c5 += nums[i].second.second;
                ++i;
                if (i > j)
                    cout << "?";
            }
            cnt += j - i;
        }
        return cnt;
    }
  private:
    long long cnt;
    int N;
    int c2, c5;
    vector<pair<int, pair<int, int>>> nums;
};

int main() {
    int n, k;
    while (cin >> n >> k) { // 注意 while 处理多个 case
        sol s(n);
        int x;
        for (int i = 0; i < n; ++i) {
            cin >> x;
            s.add(i, x);
        }
        cout << s.get(k) << '\n';
    }
}
// 64 位输出请用 printf("%lld")

详细题解请移步至 A 或 B 或 C。