题解 | 游游的数组询问

package main

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

// 计算一个数的质因子个数
func countPrimeFactors(x int) int {
    if x == 1 {
        return 0
    }
    count := 0
    for i := 2; i*i <= x; i++ {
        if x%i == 0 {
            count++
            for x%i == 0 {
                x /= i
            }
        }
    }
    if x > 1 {
        count++
    }
    return count
}

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

    var n, k int
    fmt.Fscan(reader, &n, &k)

    a := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Fscan(reader, &a[i])
    }

    // 预处理权值数组,计算整个数组的权值和
    w := make([]int, n)
    total := 0
    for i := 0; i < n; i++ {
        w[i] = countPrimeFactors(a[i])
        total += w[i]
    }


    // 滑动窗口找出长度为k的最小和
    windowSum := 0
    for i := 0; i < k; i++ {
        windowSum += w[i]
    }
    minWindow := windowSum
    for i := k; i < n; i++ {
        windowSum += w[i] - w[i-k]
        if windowSum < minWindow {
            minWindow = windowSum
        }
    }

    // 结果产出
    ans := total - minWindow
    fmt.Fprintln(writer, ans)
}