HDU 4961 Boring Sum：STL 向量模擬最近可整除/倍數元素

問題描述

給定長度 N 的數組 A。對每個位置 i：
• B[i] = i 左側最近的、能被 A[i] 整除的元素位置（不存在則為 i）。
• C[i] = i 右側最近的、是 A[i] 整數倍的元素位置（不存在則為 i）。
求 \( \sum A[B[i]] \times A[C[i]] \)。

正向掃描求 C（右側最近倍數）

維護 vector pos[val] 存儲值為 val 的位置。
從左到右遍歷 i：
• 枚舉 A[i] 的所有約數 d（\( O(\sqrt{A[i]}) \)）。
• 對於每個約數 d，將 pos[d] 中所有位置的 C 設為 i（它們的右側最近倍數就是當前 i），然後清空 pos[d]。
• 同理處理約數 A[i]/d。
• 最後將 i 加入 pos[A[i]]。

逆向掃描求 B（左側最近約數）

同理從右到左遍歷，枚舉約數，更新 pos[d] 中位置的 B 為當前 i，清空，最後加入 pos[A[i]]。

完整 C++ 代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int A[MAXN], B[MAXN], C[MAXN];
vector pos[MAXN];

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++) scanf("%d", &A[i]);
        fill(B, B+n, -1); fill(C, C+n, -1);
        for (int i = 0; i < MAXN; i++) pos[i].clear();

        // 正向求 C
        C[n-1] = n-1;
        pos[A[0]].push_back(0);
        for (int i = 1; i < n; i++) {
            int x = A[i];
            for (int d = 1; d*d <= x; d++) if (x % d == 0) {
                for (int p : pos[d]) C[p] = i;
                pos[d].clear();
                int d2 = x / d;
                if (d2 != d) {
                    for (int p : pos[d2]) C[p] = i;
                    pos[d2].clear();
                }
            }
            pos[x].push_back(i);
        }

        // 逆向求 B
        for (int i = 0; i < MAXN; i++) pos[i].clear();
        B[0] = 0;
        pos[A[n-1]].push_back(n-1);
        for (int i = n-2; i >= 0; i--) {
            int x = A[i];
            for (int d = 1; d*d <= x; d++) if (x % d == 0) {
                for (int p : pos[d]) B[p] = i;
                pos[d].clear();
                int d2 = x / d;
                if (d2 != d) {
                    for (int p : pos[d2]) B[p] = i;
                    pos[d2].clear();
                }
            }
            pos[x].push_back(i);
        }

        // 處理未找到的情況
        for (int i = 0; i < n; i++) {
            if (B[i] == -1) B[i] = i;
            if (C[i] == -1) C[i] = i;
        }
        long long ans = 0;
        for (int i = 0; i < n; i++) ans += 1LL * A[B[i]] * A[C[i]];
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度分析

• 每個元素枚舉約數 \( O(\sqrt{V}) \)，V ≤ 10^5 約 316 次。
• 每個位置最多被清空一次，總操作 \( O(N \sqrt{V}) \)。
• N ≤ 10^5，V ≤ 10^5，實測極快。

關鍵技巧

1. 約數枚舉 + 位置向量：將「最近倍數/約數」轉化為「當前值是歷史值的倍數/約數」。
2. 清空向量：一旦位置找到答案，從向量移除，保證每個位置只被處理一次。
3. 雙向掃描：左掃求右側，右掃求左側，邏輯對稱。

總結

HDU 4961 巧妙利用約數枚舉反向思維：不為每個 i 去找左右，而是為每個值維護「等待找到倍數/約數」的位置列表。STL vector 作為棧使用，清空即彈出所有待處理位置。此「掃描線 + 約數枚舉 + 向量延遲更新」模板適用於眾多「最近滿足數論關係」問題。