HDU 4135 – Co-prime [素因子+容斥]

Link

传送门

Problem

Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.
Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer.

Mean

给定一个区间[A, B],求区间内与N没有公公因子的数的个数(即gcd(X, N)==1)。

Analysis

考虑区间内与N有公公因子的数。对N进行因式分解,分解出所有素因子。然后二进制枚举素因子集合,用容斥原理计算区间内个数即可。

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll A, B, N;
vector<ll> po;

void calcpo() {
    po.clear();
    for(ll i = 2; i * i <= N; ++i) {
        if(N && N % i == 0) {
            po.push_back(i);
            while(N && N % i == 0)
                N /= i;
        }
        if(N == 1) break;
    }
    if(N > 1) po.push_back(N);
}


ll solve(ll n) {
    ll ans = 0;
    for(ll S = 1; S < (1LL << po.size()); ++S) {
        ll val = 1, cnt = 0;
        for(ll i = 0; i < po.size(); ++i) {
            if(S & (1LL << i)) {
                ++cnt;
                val *= po[i];
            }
        }
        if(cnt & 1) ans += n / val;
        else ans -= n / val;
    }
    return ans;
}

int main() {
    int T, kase = 0; scanf("%d", &T);
    while(T--) {
        scanf("%lld%lld%lld", &A, &B, &N);
        calcpo();
        printf("Case #%d: %lld\n", ++kase, (B-solve(B)) - (A-1-solve(A-1)));
    }
    return 0;
}

欢迎留言