HDU 4135 Co-prime

题目链接：​​传送门​​

多组数据问区间内与互质的数的个数
区间问题显然要转化成两个区间相减的问题
也就是的答案减去的答案
这里反过来求不互质的数的个数
筛法可以提示我们
分解质因数，通过质因子来筛数
所以我们存下这个的质因子
用二进制的方法枚举每种情况
但是这样筛可能会有重复
比如会被和各筛一遍
这就用到了容斥原理奇数加偶数减
不互质的数的个数直接质因子相乘做除法就好了
然后
就没了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
int pri[A], n, T;
ll a, b;
ll sol(ll n, int cnt, ll ans = 0) {
    for (int i = 1; i < (1 << cnt); i++) { //二进制枚举所有情况
        int tmp = 1, js = 0;
        for (int j = 0; j < cnt; j++) {
            if ((i >> j) % 2 == 0) continue;
            js++; tmp *= pri[j];
        }
        if (js & 1) ans += n / tmp;
        else ans -= n / tmp;
    }
    return n - ans;
}

int main(int argc, char const *argv[]) {
    cin >> T;
    for (int k = 1; k <= T; k++) {
        cin >> a >> b >> n; int cnt = 0;
        for (int i = 2; i * i <= n; i++) //筛质因子
            if (n % i == 0) {
                while (n % i == 0) n /= i;
                pri[cnt++] = i;
            }
        if (n != 1) pri[cnt++] = n;
        cout << "Case #" << k << ": " << sol(b, cnt) - sol(a - 1, cnt) << endl;
    }
}