HDU 5288 OO's Sequence：因數位置記錄與區間貢獻計算

問題描述

給定數組 A[1..n]，定義 f(l,r) 為區間 [l,r] 中「沒有其他數能整除它」的元素個數。求所有區間的 f(l,r) 之和模 1e9+7。n ≤ 1e5, a_i ≤ 10000。

核心轉化

對每個位置 i，考慮它作為「無因數元素」被計數的區間範圍。設 L[i] 為 i 左側最近的因數位置（不存在則 0），R[i] 為右側最近的因數位置（不存在則 n+1）。則 i 會被計數的區間左端點 ∈ [L[i]+1, i]，右端點 ∈ [i, R[i]-1]。貢獻為 (i-L[i]) * (R[i]-i)。

高效計算 L[i], R[i]

因 a_i ≤ 10000，可用數組 pos[v] 記錄值 v 最近出現的位置。遍歷 i=1..n：

• 枚舉 a_i 的所有因數 d（O(√a_i)），查詢 pos[d] 更新 L[i]。
• 更新 pos[a_i] = i。

反向遍歷同理得 R[i]。

代碼實現

const int MOD = 1e9+7;
int a[100010], L[100010], R[100010], pos[10010];

int main() {
    int n;
    while (scanf("%d",&n)==1) {
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        memset(pos,0,sizeof(pos));
        for (int i=1;i<=n;i++) {
            L[i]=0;
            for (int d=1; d*d<=a[i]; d++) if (a[i]%d==0) {
                if (pos[d]) L[i]=max(L[i],pos[d]);
                if (pos[a[i]/d]) L[i]=max(L[i],pos[a[i]/d]);
            }
            pos[a[i]]=i;
        }
        memset(pos,0,sizeof(pos));
        for (int i=n;i>=1;i--) {
            R[i]=n+1;
            for (int d=1; d*d<=a[i]; d++) if (a[i]%d==0) {
                if (pos[d]) R[i]=min(R[i],pos[d]);
                if (pos[a[i]/d]) R[i]=min(R[i],pos[a[i]/d]);
            }
            pos[a[i]]=i;
        }
        long long ans=0;
        for (int i=1;i<=n;i++)
            ans = (ans + 1LL*(i-L[i])*(R[i]-i)) % MOD;
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度

每個元素枚舉因數 O(√a_i)，總時間 O(n √A)，A=10000 時約 1e7 操作，極快。

總結

HDU 5288 巧妙將「區間無因數」轉化為「單元素貢獻區間」，利用因數枚舉 + 最近位置記錄，線性掃描得出答案。此類「每個元素獨立貢獻」的思想廣泛適用於區間統計問題。