#12568. 节能采样与公约数警报

节能采样与公约数警报

题目:节能采样与公约数警报

🗂️ 任务信息 时间限制:1s 内存限制:512 MB 难度:⭐⭐⭐(滑动窗口 + gcd)


📝 题目描述

在一座实验基地中,传感器每秒产生一次“能耗值”。工程师要进行一次​连续采样​,采样必须包含 恰好 (K) 秒的数据。

给定长度为 (n) 的正整数数组 a,第 (i) 秒能耗为 (a_i)。

你需要完成两件事:

  1. 在所有长度恰好为 (K) 的连续子数组中,找到​最小的子数组和​,记为

    SminS_{\min}

  2. 设取得最小和的那段子数组为 (W)(若最小和出现多次,取最靠左的一段),计算

    G=gcd(W 中所有元素)G=\gcd(\text{W 中所有元素})

    判断 (Smin)(G)(S_{\min}) 与 (G) 是否存在​大于 1 的公约数​,即判断:

    gcd(Smin,G)>1\gcd(S_{\min}, G) > 1


📥 输入格式

第一行输入两个整数:n K 第二行输入 n 个正整数:a1 a2 ... an


📤 输出格式

输出两行:

  • 第一行输出最小子数组和(Smin)(S_{\min})
  • 第二行输出 YESNO
    • YES 表示(gcd(S_min,G)>1) (\gcd(S\_{\min}, G) > 1)
    • NO 表示 (gcd(S_min,G)=1)(\gcd(S\_{\min}, G) = 1)

📚 样例

输入:

8 3
6 10 15 3 5 7 2 9

输出:

14
NO

说明:长度为 3 的窗口和最小的是 [5,7,2],和为 14。 该窗口元素 gcd 为 (\gcd(5,7,2)=1),所以 (\gcd(14,1)=1),输出 NO


📏 数据范围(建议)

  • (1Kn2×105)(1 \le K \le n \le 2\times 10^5)
  • (1ai109)(1 \le a_i \le 10^9)
  • 子数组和使用 64 位整数(long long

💡 训练点

  • 定长滑动窗口求最小和((O(n)))
  • gcd 运算((O(K)),只对最优窗口算一次)