UVA 11426 GCD Extreme 歐拉函數篩法求和

關鍵：f(n) = ∑_{d|n} d × φ(n/d)，其中 d 遍歷 n 的因子。

線性篩預處理

const int N = 4000000;
int phi[N+5]; ll f[N+5], s[N+5];
void phi_table(int n) {
    for (int i = 2; i <= n; i++) phi[i] = 0;
    phi[1] = 1;
    for (int i = 2; i <= n; i++) if (!phi[i])
        for (int j = i; j <= n; j += i) {
            if (!phi[j]) phi[j] = j;
            phi[j] = phi[j] / i * (i-1);
        }
}
int main() {
    phi_table(N);
    for (int i = 1; i <= N; i++)
        for (int j = i*2; j <= N; j += i)
            f[j] += i * phi[j/i];
    s[2] = f[2];
    for (int i = 3; i <= N; i++) s[i] = s[i-1] + f[i];
    int n; while (scanf("%d",&n) && n) printf("%lld\n", s[n]);
}

複雜度分析

• φ 篩：O(N log log N)
• f 數組計算：調和級數 ∑ N/i = O(N log N)
• 查詢 O(1)
• 總預處理 ~1 秒內完成，N=4e6 記憶體 ~100MB 可接受

關鍵優化：內層循環 j = i*2 從 2i 開始，避免 i=j 產生 gcd(n,n)=n 的情況（題目要求 i≠j）。