小美的区间删除

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

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)
    

    

a1 = input().split(' ')
lng = int(a1[0])
b = int(a1[1])
l_data = input().split()
l_data = [int(x) for x in l_data] def chengji(lng, l_data):
    x = 1  for i in range(lng):
        x = x*l_data[i] return x
ind = 0 for i in range(1,lng): for j in range(lng-i+1):
        data = l_data.copy()
        data[j:i+j] = [1] * i
        x = chengji(lng,data) if x/10**b == int(x/10**b) and x/100**b != int(x/100**b):
            ind += 1  print('第{}个方案,删除{}'.format(ind,l_data[j:i+j]))

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] cnt2 = new int[n];
        int[] cnt5 = new int[n];
        long sum2 = 0, sum5 = 0;
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int[] cnt = cnt(a);
            sum2 += cnt2[i] = cnt[0];
            sum5 += cnt5[i] = cnt[1];
        }
        if (sum2 < k || sum5 < k) {
            System.out.println(0);
            return;
        }
        int l = 0;
        long ans = 0;
        for (int r = 0; r < n; r++) {
            sum2 -= cnt2[r];
            sum5 -= cnt5[r];
            while (sum2 < k || sum5 < k) {
                ans += r - l;
                sum2 += cnt2[l];
                sum5 += cnt5[l];
                l++;
            }
        }
        ans += (long) (n - l) * (1 + n - l) / 2;
        System.out.println(ans);
    }

    static int[] cnt(int num) {
        int res2 = 0;
        while (num % 2 == 0) {
            res2++;
            num /= 2;
        }
        int res5 = 0;
        while (num % 5 == 0) {
            res5++;
            num /= 5;
        }
        return new int[]{res2, res5};
    }
}

import java.util.Scanner;

public class Main  {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n,k;
        n = scan.nextInt();
        k = scan.nextInt();
        int[] c5 = new int[n];
        int[] c2 = new int[n];
        int count5 = 0;
        int count2 = 0;
        for (int i = 0; i < n; i++) {
            int c = scan.nextInt();
            int t = c;
            int i2 = 0,i5 = 0;
            while(t>0&&(t&1)==0) {
                i2++;
                t>>=1;
            }
            t = c;
            while(t>0&&(t%5==0)){
                i5++;
                t/=5;
            }
            c2[i] = i2;
            count2+=i2;
            c5[i] = i5;
            count5+=i5;
        }
        if(Math.min(count2,count5)<k) {
            System.out.println(0);
            return;
        }
        long ans = 0;
        int i=0,j=0;
        int n2 = c2[0],n5 = c5[0];
        while(j<n){
            if(j<n&&Math.min(count2-n2,count5-n5)>=k) {
                ans += (j-i)+1;
                j++;
                if(j<n){
                    n2+=c2[j];
                    n5+=c5[j];
                }
            }else  {
                //如果cj过大i会超越j
                while (i <= j && Math.min(count2 - n2, count5 - n5) < k) {
                    n5 -= c5[i];
                    n2 -= c2[i];
                    i++;
                }
                if (i > j) {
                    j = i;
                }
            }
        }
        System.out.println(ans);

    }
}

//5 2
//2 5 3 4 20
//10 2
//1 2 2 4 5 1 2 2 5 1