Codeforces 359D - Pair of Numbers：最大公約數子段與雙指針優化

問題重述

給定長度 n 的正整數數組 a[1..n]。找出所有區間 [l, r] 使得：

1. 區間內存在某個 j (l ≤ j ≤ r)，使 a[l..r] 所有元素均能被 a[j] 整除
2. r - l 取得最大值

輸出滿足條件的區間個數、最大長度 r-l，以及所有最優區間的左端點 l（升序）。

關鍵觀察

條件等價於：區間內最小值能整除區間內所有元素。（因為若存在 a[j] 整除所有元素，則 a[j] 必為區間最小值；反之，若最小值整除所有元素，取 j 為最小值位置即可。）

線性掃描算法

對每個位置 i 作為候選「最小值兼除數」，向左右擴展直到遇到不能被 a[i] 整除的元素。記錄擴展後的區間 [L, R]，長度為 R - L - 1（代碼中 ri - le - 2）。

為避免重複計算，掃描到 i 後直接跳至 R 繼續（類似 KMP/Manacher 的跳躍優化），總時間 O(n)。

C++ 實現

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 300009;
int a[N], ans[N];

int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        int bestLen = -1, cnt = 0;
        for (int i = 1; i <= n; ) {
            int le = i, ri = i;
            // 向左擴展
            while (le >= 1 && a[le] % a[i] == 0) --le;
            // 向右擴展
            while (ri <= n && a[ri] % a[i] == 0) ++ri;
            int len = ri - le - 2; // 實際區間長度 r-l
            if (len > bestLen) {
                bestLen = len;
                cnt = 0;
            }
            if (len == bestLen) ans[cnt++] = le + 1;
            i = ri; // 跳躍優化
        }
        printf("%d %d\n", cnt, bestLen);
        for (int i = 0; i < cnt; ++i) printf("%d ", ans[i]);
        puts("");
    }
    return 0;
}

樣例解析

輸入: 5
      4 6 9 3 6
輸出: 1 3
      2

區間 [2,4]（元素 6,9,3），最小值 3 整除所有元素，長度 3 為最大。

複雜度

• 時間：O(n) — 每個元素最多被訪問常數次
• 空間：O(n)