HDU 4135 ( 容斥 )-JZTXT

题意：

求区间 $[a,b]$ 中与 n 互质的数的个数，其中 $1 <= a, b, c <= 2^{31}$。

思路：

容斥定理最常用于求区间 $[a,b]$ 中与 n 互质的数的个数问题。
该问题的答案显现为：$[1, b]$ 中与n互质的个数 $- [1,a-1]$中与n互质的个数.
那么这里只需要考虑它的一个子问题：求小于等于 m 且与 n 互素的数的个数。
只要解决这个，我们就可以解决这个问题。
那么这个问题怎么解？
显然，当 m = n 时，这是一个普通的欧拉函数问题。但当 m != n 时，我们一般考虑将 n 质因数分解。
例：首先考虑 n 为素数幂 : $n = p ^ k$, 显然答案就 = m - $ m \over p$。
然后考虑 n 为2个素数幂 : n = ${p_1}$^${k_1}$ + $p_2$^$k_2$, 显然答案就
= m - (m / $p_1$ + m / $p_2$ - $m/(p_1 * p_2)$)。
很明显对 n 分解质因数后，容斥集合（奇加偶减）即可求出该子问题。

AC代码：

// -----------------
//#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <algorithm>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
#define endl '\n'
#define int long long 
using namespace std;

const int N = 1e6 + 7;
int a,b,n,kkk;

int primes[N],cnt;
bool st[N];
void initpr(int n)  // 质数筛
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i]) primes[++ cnt] = i;
        for(int j = 1; j <= cnt && primes[j] * i <= n; j ++)
        {
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}

int cntt,fa[N];
void get(int n)  // 分解n的质因子
{
    cntt = 0;
    for(int i = 1; primes[i] * primes[i] <= n && i <= cnt; i ++)
    {
        if(n % primes[i] == 0)
        {
            fa[cntt ++] = primes[i];
            while(n % primes[i] == 0) n /= primes[i];
        }
    }
    if(n != 1) fa[cntt ++] = n;
}

int cal(int m, int cntt)  
{
    int res = 0;
    for(int i = 1; i < (1 << cntt); i ++)  // 枚举子集
    {
        int sum = 0, tmp = 1;
        for(int j = 0; j < cntt; j ++)
        {
            if(i & (1 << j))
            {
                sum ++;
                tmp *= fa[j];
            }
        }
        // 容斥原理，奇加偶减。
        if(sum % 2) res += m / tmp;
        else res -= m / tmp;
    }
    return res;
}

void solve()
{
    cin >> a >> b >> n;
    int ans = 0;
    get(n);
    ans = b - (a - 1) - cal(b, cntt) + cal(a - 1, cntt);
    cout << "Case #" << kkk << ": " << ans << endl;
}

signed main()
{
    IOS initpr(100010);
    int T = 1;
    cin >> T;
    while(T --) { kkk ++; solve(); }
    return 0;
}