LightOJ 1007：歐拉函數平方和前綴和

題目大意

定義 score(x) = φ(x)^2，其中 φ(x) 為歐拉函數（與 x 互質且小於 x 的正整數個數）。給多組查詢 [a, b]，求區間內 score 之和。T ≤ 10^5，a,b ≤ 5×10^6。

解法

預處理：線性篩法求出 1~5,000,000 的 φ 值，計算前綴和 sum[i] = sum[i-1] + φ(i)^2（需用 unsigned long long 防溢出）。每組查詢 O(1) 回答 sum[b] - sum[a-1]。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000010;
int phi[MAXN], minPrime[MAXN];
unsigned long long prefix[MAXN];

void linearSieve() {
    for (int i = 1; i < MAXN; i++) minPrime[i] = i;
    for (int i = 2; i < MAXN; i++) {
        if (minPrime[i] == i) {
            if (1LL * i * i < MAXN)
                for (int j = i * i; j < MAXN; j += i)
                    if (minPrime[j] == j) minPrime[j] = i;
        }
    }
    phi[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        int p = minPrime[i], j = i / p;
        phi[i] = phi[j];
        if (j % p) phi[i] *= (p - 1);
        else phi[i] *= p;
    }
    for (int i = 1; i < MAXN; i++)
        prefix[i] = prefix[i-1] + 1ULL * phi[i] * phi[i];
}

int main() {
    linearSieve();
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        int a, b; scanf("%d%d", &a, &b);
        printf("Case %d: %llu\n", cas, prefix[b] - prefix[a-1]);
    }
    return 0;
}