HDU 4135 Co-prime

题目链接

题意：求区间[a,b]中与m互素的数字个数

一、题目分析

考虑[1,a-1]和[1,b]两个区间与m互素的个数，答案就是二者之差(类似前缀和？)。

容斥原理经典问题：求1-n中与m互素的数的个数

互素的个数等于总数减去不互素的个数,如果\(1-n\)中某个数与\(m\)不互素，那么一定可以被\(m\)的某个因子整除，所以先枚举\(m\)的所有素因子。

举个例子，\(m=12,n=8\)，\(12\)的素因子是\(2，3\)，

\(1\sim 8\)中有几个是\(2\)的倍数呢？\(S_2=8/2=4\);
\(1\sim 8\)中有几个是\(3\)的倍数呢？\(S_3=8/3=2\);

\(1\sim 8\)之间与\(12\)互素的个数是\(2+4=6\)个数字吗？

\(1\sim 8\)之间与\(12\)不互素的是\(2，3，4，6，8\)，共\(5\)个数字，这是因为同为\(2\)和\(3\)的倍数的\(6\)被计算了两次，所以要再减去一次\(S_6=8/6=1\),结果是 $$\large 8/2+8/3-8/(2*3)=4+2-1=5$$

这是经典的容斥原理啊，如果是奇数个组合，那么符号是+；如果是偶数个组合，那么符号是-；

二、实现代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

//返回1-m中与n互素的数的个数
vector<LL> p;
LL cal(LL n, LL m) {
    p.clear();
    for (int 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); //求n的素因子

    int num = p.size(); //素因子的个数
    LL s = 0;           // 1到m中与n不互素的数的个数

    //枚举子集，不能有空集，所以从1开始
    for (LL i = 1; i < 1 << num; i++) { //从1枚举到(2^素因子个数)
        LL cnt = 0;
        LL t = 1;
        for (LL j = 0; j < num; j++) { //枚举每个素因子
            if (i & (1 << j)) {        //有第i个因子
                cnt++;                 //计数
                t *= p[j];             //乘上这个质因子
            }
        }
        //容斥原理
        if (cnt & 1) //选取个数为奇数，加
            s += m / t;
        else //选取个数为偶数，减
            s -= m / t;
    }
    return m - s; //返回1-m中与n互素的数的个数
}

int main() {
    //加快读入
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T, ca = 0;
    cin >> T;

    while (T--) {
        LL m, a, b;
        cin >> a >> b >> m; //求区间[a,b]中与m互素的数字个数
        //计算[1,a-1]之间与m互素的个数
        //计算[1,  b]之间与m互素的个数
        LL ans = cal(m, b) - cal(m, a - 1);
        printf("Case #%d: %lld\n", ++ca, ans);
    }
    return 0;
}