HDU 5288 OO's Sequence：區間倍數關係與前綴統計解法詳解

問題描述

給定一個長度為 n 的序列 a[1..n]。定義函數 f(l, r) 為區間 [l, r] 中，不被該區間內任意其他數整除的元素個數。要求計算所有區間 f(l, r) 的總和（模 1e9+7）。

核心思路

對於每個元素 a[i]，我們尋找其能作為「不被區間內其他數整除」的最大區間範圍 [l[i], r[i]]。若 a[i] 在區間 [l, r] 中滿足條件，則該區間必須包含 i，且 l[i] ≤ l ≤ i ≤ r ≤ r[i]。因此，以 a[i] 為合法元素的區間數量為 (i - l[i] + 1) * (r[i] - i + 1)。總答案即為所有 i 的此乘積之和。

求解 l[i] 與 r[i]

• 右邊界 r[i]：從左到右遍歷。維護 pre[v] 記錄值 v 最後出現的位置。對於當前 a[i]，枚舉其所有倍數 j，若 pre[j] 存在且 r[pre[j]] 尚未確定（初始為 n），則說明 a[pre[j]] 的右邊界受限於當前 i，設 r[pre[j]] = i - 1。最後更新 pre[a[i]] = i。
• 左邊界 l[i]：從右到左遍歷，邏輯對稱。維護 last[v]，枚舉倍數 j，若 last[j] 存在且 l[last[j]] 尚未確定（初始為 1），則設 l[last[j]] = i + 1。更新 last[a[i]] = i。

複雜度分析

枚舉倍數的總次數為 ∑ (MAX_A / a[i])，其中 MAX_A = 10000。調和級數近似 O(MAX_A log MAX_A)，對於 n ≤ 1e5 完全可行。空間複雜度 O(MAX_A + n)。

參考代碼 (C++)

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 100010;
const int mod = 1e9+7;
int a[maxn];
typedef long long ll;
ll last[maxn], pre[maxn], l[maxn], r[maxn];

int main() {
    int n;
    while (~scanf("%d", &n)) {
        memset(last, 0, sizeof(last));
        memset(pre, 0, sizeof(pre));
        for (ll i = 1; i <= n; i++) {
            l[i] = 1; r[i] = n;
            scanf("%d", &a[i]);
            for (ll j = a[i]; j < maxn/10; j += a[i])
                if (pre[j] != 0 && r[pre[j]] == n)
                    r[pre[j]] = i - 1;
            pre[a[i]] = i;
        }
        for (ll i = n; i >= 1; i--) {
            for (ll j = a[i]; j < maxn/10; j += a[i])
                if (last[j] != 0 && l[last[j]] == 1)
                    l[last[j]] = i + 1;
            last[a[i]] = i;
        }
        ll ans = 0;
        for (ll i = 1; i <= n; i++)
            ans = (ans + (((i - l[i] + 1) % mod) * ((r[i] - i + 1) % mod)) % mod) % mod;
        printf("%lld\n", ans);
    }
    return 0;
}