Python3 解法, 执行用时: 1033ms, 内存消耗: 7608K, 提交时间: 2023-08-12 12:55:23

def atMostN(nums,k):
    left, right = 0, 0
    five_count, zero_count, even_count = 0, 0, 0
    res = 0
    while right < n:
        num = nums[right]
        while num % 10 == 0:
            zero_count += 1
            num //= 10
        while num % 5 == 0:
            five_count += 1
            num //= 5
        while num % 2 == 0:
            even_count += 1
            num //= 2
        while left < n and zero_count + min(five_count,even_count) > k:
            # pop left
            num = nums[left]
            while num % 10 == 0:
                zero_count -= 1
                num //= 10
            while num % 5 == 0:
                five_count -= 1
                num //= 5
            while num % 2 == 0:
                even_count -= 1
                num //= 2
            left += 1
        res += (right - left + 1)
        right += 1
    return res


T = int(input())
for _ in range(T):
    n,k = list(map(int,input().split()))
    nums = list(map(int,input().split()))
    count = atMostN(nums,k)
    if k > 0:
        count -= atMostN(nums,k-1)
    print(count)

Java 解法, 执行用时: 1509ms, 内存消耗: 31600K, 提交时间: 2023-08-12 12:54:45

import java.io.*;
import java.util.Arrays;
import java.util.Scanner;
public class Main
{
	public static void main(String[] args) throws IOException
	{
        Scanner s=new Scanner(System.in);
        while(s.hasNext()){
    		int t=s.nextInt();
    		while(t-->0)
    		{
    			long n=s.nextLong(),k=s.nextLong();
    			long a[]=new long[(int) (n+10)];
    			a[0]=1;
    			for(int i=1;i<=n;i++)
    			{
    				a[i]=s.nextLong();
    				a[i]*=a[i-1];
    			}
    			long ans=0;
    			for(int i=1;i<=n;i++)
    			{
    				long tl=i,tr=n;
    				while(tl<tr)
    				{
    					long mid=tl+tr>>1;
    					if(check(a[(int) mid]/a[i-1])>=k) tr=mid;
    					else tl=mid+1;
    				}
    				long ans2=tl;
    				tl=i;
    				tr=n;
    				while(tl<tr)
    				{
    					long mid=tl+tr+1>>1;
    					if(check(a[(int) mid]/a[i-1])<=k) tl=mid;
    					else tr=mid-1;
    				}
    				if(check(a[(int) ans2]/a[i-1])==k)
    				ans+=tl-ans2+1;
    			}
    			System.out.println(ans);
    		
    	}
         }
     }

	private static long check(long a)
	{
		long res=0;
		while(true)
		{
			if(a%10==0)
			res++;
			else
			break;
			a/=10;
			if(a==0)break;
		}
		return res;
	}
}

Go 解法, 执行用时: 195ms, 内存消耗: 5476K, 提交时间: 2023-08-12 12:53:43

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var t int
	fmt.Fscan(in, &t)
	for ; t > 0; t-- {
		var n, k, a int
		fmt.Fscan(in, &n, &k)
		count2, count5 := make([]int, n), make([]int, n)
		preSum2, preSum5 := make([]int, n+1), make([]int, n+1)
		for i := 0; i < n; i++ {
			fmt.Fscan(in, &a)
			for a%2 == 0 {
				count2[i]++
				a /= 2
			}
			for a%5 == 0 {
				count5[i]++
				a /= 5
			}
			preSum2[i+1], preSum5[i+1] = preSum2[i]+count2[i], preSum5[i]+count5[i]
		}

		lowerBound := sort.SearchInts
		upperBound := func(a []int, x int) int { return sort.SearchInts(a, x+1) }

		ans := 0
		for i := 1; i <= n; i++ {
			v2, v5 := k+preSum2[i-1], k+preSum5[i-1]

			lower2, upper2 := lowerBound(preSum2, v2), upperBound(preSum2, v2)-1
			lower5, upper5 := lowerBound(preSum5, v5), upperBound(preSum5, v5)-1

			l := max(lower2, lower5)
			r := max(upper2, upper5)
			l = max(l, i)
			if l == n+1 {
				continue
			}
			ans += r - l + 1
		}
		fmt.Fprintln(out, ans)
	}
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}