Go 解法, 执行用时: 255ms, 内存消耗: 8164K, 提交时间: 2023-08-12 09:58:52

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
}

Python3 解法, 执行用时: 1225ms, 内存消耗: 46492K, 提交时间: 2023-08-12 09:57:32

from collections import defaultdict
t = int(input())
def solve():
    n, k = map(int, input().split())
    *nums, = map(int, input().split())
    hm2 = defaultdict(int)
    hm5 = defaultdict(int)
    for i in range(len(nums)):
        while nums[i] % 2 == 0:
            nums[i] //= 2
            hm2[i] += 1
        while nums[i] % 5 == 0:
            nums[i] //= 5 
            hm5[i] += 1
    def f(k):
        l = r = 0
        c2  = c5 = 0
        res = 0
        while r < len(nums):
            c2 += hm2[r]
            c5 += hm5[r]
            while l <= r and min(c2, c5) > k:
                c2 -= hm2[l]
                c5 -= hm5[l]
                l += 1
            res += r - l + 1
            r += 1
        return res 
    print(f(k) - f(k - 1))

for _ in range(t):
    solve()