HDU 1286 找新朋友：篩法計算與 N 互質的數字個數

篩法實現

int find_divisors(int n, int d[]) {
    int cnt = 0;
    for (int i = 2; i <= n/2; i++)
        if (n % i == 0) d[cnt++] = i;
    return cnt;
}
int count_new_friends(int n, int d[], int len) {
    bool sieve[33000] = {0};
    for (int i = 0; i < len; i++) {
        for (int j = d[i]; j < n; j += d[i])
            sieve[j] = true; // 標記有公約數
    }
    int cnt = 0;
    for (int i = 1; i < n; i++) if (!sieve[i]) cnt++;
    return cnt;
}

優化：直接計算 φ(N)

分解 N = ∏ p_i^{k_i}，φ(N) = N ∏ (1 - 1/p_i)。對多測試用例（CN<10000），預篩素數至 32768，每查詢 O(√N) 分解極快。

int phi(int n) {
    int res = n;
    for (int p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            res -= res / p;
        }
    }
    if (n > 1) res -= res / n;
    return res;
}

複雜度對比

• 篩法標記：O(N log log N) 每查詢，N≤32767 尚可但較慢。
• 歐拉函數公式：O(√N) 每查詢，10000 用例總計 ~10^6 操作，瞬間通過。