HDU 4135 Co-prime：容斥原理求區間互素數個數

問題描述

給定整數 n 和區間 [a, b]，求區間內與 n 互素的數的個數。多測試用例。

容斥原理轉化

設 n 的質因子為 p_1..p_k。區間 [1, x] 中與 n 不互素的數 = 能被至少一個 p_i 整除的數。由容斥原理：

cnt(x) = Σ_{非空子集 S} (-1)^{|S|+1} * floor(x / ∏_{i∈S} p_i)

答案 = cnt(b) - cnt(a-1)。再用 (b-a+1) - 不互素數 得互素數，或直接算互素數（符號相反）。

代碼實現

vector p; // 質因子
ll solve(ll n, ll r) { // [1,r] 中與 n 互素的數
    p.clear();
    for (ll i=2; i*i<=n; i++)
        if (n%i==0) { p.push_back(i); while(n%i==0) n/=i; }
    if (n>1) p.push_back(n);
    ll notCoprime = 0;
    int sz = p.size();
    for (int mask=1; mask < (1<>i & 1) { prod *= p[i]; bits++; }
        ll c = r / prod;
        if (bits & 1) notCoprime += c; else notCoprime -= c;
    }
    return r - notCoprime;
}

複雜度

質因子數 ≤ 9（2*3*5*7*11*13*17*19*23 > 1e9），子集數 ≤ 511。每查詢 O(2^k)，極快。