HDU 4961 Boring Sum 高效解法：因數向量預處理

優化點

同 ID 208655，此處強調使用 vector divisors[MAXV] 預存每個數的所有因數，掃描時直接遍歷向量，避免重複開根號枚舉因數，常數項更小。

預處理

const int MAXV = 100000;
vector divisors[MAXV+1];
void init() {
    for (int i=1;i<=MAXV;++i)
        for (int j=i;j<=MAXV;j+=i)
            divisors[j].push_back(i);
}

掃描邏輯

// Left
vector last(MAXV+1, 0);
for (int i=1;i<=n;++i) {
    int pos = 0;
    for (int d : divisors[a[i]]) pos = max(pos, last[d]);
    b[i] = pos ? a[pos] : a[i];
    for (int d : divisors[a[i]]) last[d] = i;
}
// Right
vector nxt(MAXV+1, INF);
for (int i=n;i>=1;--i) {
    int pos = INF;
    for (int d : divisors[a[i]]) pos = min(pos, nxt[d]);
    c[i] = (pos==INF) ? a[i] : a[pos];
    for (int d : divisors[a[i]]) nxt[d] = i;
}

複雜度

預處理 O(V log V)。主循環每個 a[i] 遍歷其因數個數 d(a[i])，總操作數 Σ d(a[i]) 遠小於 n * sqrt(V)。