解题思路

• 将问题转化：一个区间乘积的二进制末尾有 ≥k 个 0，等价于该区间内所有元素的 2 的因子个数之和 ≥ k。 记 v2(x) 为 x 被 2 整除的次数（即二进制尾随零个数），则区间 [l,r] 满足条件 ⇔ sum(v2(a[l..r])) ≥ k。

• 算法：

  1. 预处理得到数组 b[i] = v2(a[i])（非负整数）；
  2. 因为 b[i] ≥ 0，可用 滑动窗口/双指针：右指针不断右移累加窗口和 s；当 s ≥ k 时，尝试移动左指针缩小窗口并更新答案的最小长度。

• 若整个数组 b 的总和都 < k，则不存在满足条件的子数组，输出 -1（若题目平台有其他约定，可按平台改动）。

复杂度分析

• 预处理 v2：每个数最多除以 2 共 O(log a_i) 次，但 a_i ≤ 1e9，实际很小；可视为 O(n) 级常数因子。
• 双指针遍历每个元素至多进入/移出窗口一次：时间复杂度 O(n)。
• 仅使用若干指针与少量变量：空间复杂度 O(1)（若将 b 复用在原数组或边算边用，可视为 O(1) 额外空间）。

代码实现

Python

# -*- coding: utf-8 -*-
import sys

# 计算二进制尾随零个数，即因子2的个数 v2(x)
def v2(x: int) -> int:
    cnt = 0
    # a_i >= 1，不会出现 0
    while (x & 1) == 0:  # 等价于 x % 2 == 0，但位运算更快
        cnt += 1
        x >>= 1
    return cnt

# 求最短满足 sum(v2) >= k 的子数组长度，不存在则返回 -1
def solve(a, k: int) -> int:
    n = len(a)
    b = [v2(x) for x in a]  # 预处理 v2

    left = 0
    s = 0
    ans = n + 1  # 初始为不可能的大值

    for right in range(n):
        s += b[right]
        # 尝试收缩左端，使长度最短
        while s >= k:
            ans = min(ans, right - left + 1)
            s -= b[left]
            left += 1

    return ans if ans <= n else -1

def main():
    data = sys.stdin.read().strip().split()
    it = iter(map(int, data))
    n = next(it); k = next(it)
    a = [next(it) for _ in range(n)]
    print(solve(a, k))

if __name__ == "__main__":
    main()

Java

// ACM 风格，类名为 Main
// 思路：预处理 v2(a[i]) 后用双指针（滑动窗口）找最短子数组
import java.io.*;
import java.util.*;

public class Main {
    // 计算 v2(x)：x 中因子 2 的个数（尾随零个数）
    static int v2(long x) {
        int c = 0;
        while ((x & 1L) == 0L) { // 当最低位为 0 时，说明可被 2 整除
            c++;
            x >>>= 1; // 无符号右移，保持非负
        }
        return c;
    }

    // 返回最短长度；若不存在则返回 -1
    static int solve(int[] a, int k) {
        int n = a.length;
        int[] b = new int[n];
        for (int i = 0; i < n; i++) b[i] = v2(a[i]);

        int left = 0, sum = 0, ans = n + 1;
        for (int right = 0; right < n; right++) {
            sum += b[right];
            while (sum >= k) {
                ans = Math.min(ans, right - left + 1);
                sum -= b[left++];
            }
        }
        return ans <= n ? ans : -1;
    }

    public static void main(String[] args) throws Exception {
        // 根据数据范围使用 BufferedReader + StringTokenizer
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());

        int ans = solve(a, k);
        System.out.println(ans);
    }
}

C++

// 思路：将每个 a[i] 映射为 b[i]=v2(a[i])，再用滑动窗口求最短长度
#include <bits/stdc++.h>
using namespace std;

// 计算 v2(x)：x 含有的 2 的因子个数（即二进制尾随零个数）
static inline int v2(long long x) {
    int c = 0;
    while ((x & 1LL) == 0LL) { // 最低位为 0 则可继续除以2
        ++c;
        x >>= 1;
    }
    return c;
}

// 返回最短长度；若不存在则返回 -1
int solve(const vector<long long>& a, int k) {
    int n = (int)a.size();
    vector<int> b(n);
    for (int i = 0; i < n; ++i) b[i] = v2(a[i]);

    int left = 0, ans = n + 1;
    long long s = 0; // 累计 v2 之和
    for (int right = 0; right < n; ++right) {
        s += b[right];
        while (s >= k) {
            ans = min(ans, right - left + 1);
            s -= b[left++];
        }
    }
    return (ans <= n) ? ans : -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    int ans = solve(a, k);
    cout << ans << "\n";
    return 0;
}

题目描述

K0序列是指，序列中元素的乘积转换为2进制后末尾至少有 $k$ 个0。

给定一个长度为 $n$ 的序列 $a$ 和 $k$ 值，求其中为K0序列的连续子序列的最小长度。

输入描述

输入第一行两个正整数 $n，k$ 。（$3 \leq n \leq 10^5，1 \leq k \leq 10^5$）

输入第二行 $n$ 个正整数,第 $i$个为 $a_i$ 。（$1 \leq a_i \leq 10^9$）

输出描述

输出一个正整数 ，表示连续子序列的二进制不小于 $k$ 的长度。

样例

样例输入

7 3
1 2 3 4 5 6 7

样例输出

3