hdu4135 Co-prime 题解

题意：

\(T\) 组数据，每组给出 \(a,b,n\) ，求区间 \([a,b]\) 中有多少个数与 \(n\) 互质。

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.

\(1 \le a\le b\le 10^{15},~1 \le n \le 10^9\)

首先一个常见转化 \(\text{ans} = f(b)-f(a-1)\)

其中 \(f(k)\) 表示 \([1,k]\) 中与 \(n\) 互质的数的个数

注意到如果 \(x\) 与 \(n=\prod\limits_{1\le i \le t} p_i^{k_i}\) 互质，

则对于任意 \(p_i\) ，均有 \(p_i \nmid x\)

直接去算并不好算，考虑容斥

下面会涉及一些定义，我放在了文章末尾

在这题里，“坏性质”就是与 \(p_i\) 不互质

我们 \(O(2^t)\) 枚举 \(S\) （显然 \(t \le \log n\) ）

举个例子，假设 \(S_i = \{1,2\}\) ，

则表示能放到 \(N(S)\) 中的一定要有 \(P_1,P_2\) 的性质

在这题里，就是能放到 \(N(S)\) 里的 \(x\) 满足 \(p_1 \mid x \,\land \, p_2 \mid x\)

时间复杂度为 \(O(Q\times 2^{t})\)

代码采用比较好理解的位运算写法

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(25)

int pcnt,p[N];
void getp(int n)
{
    pcnt=0;
    for(int i=2; i<=n/i; i++)
    {
        if(n%i==0) p[++pcnt]=i;
        while(n%i==0) n/=i;
    }
    if(n>1) p[++pcnt]=n;
}
int solve(int m)
{
    int ans=m;
    for(int i=1; i<(1<<pcnt); i++)
    {
        int res=1,c=0;
        for(int j=0; j<pcnt; j++)
            if(i&(1ll<<j)) ++c,res*=p[j+1];
        if(c&1) ans-=m/res;
        else ans+=m/res;
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q,a,b,n;
    scanf("%lld",&Q);
    for(int t=1; t<=Q; t++)
    {
        scanf("%lld%lld%lld",&a,&b,&n); getp(n);
        printf("Case #%lld: %lld\n",t,solve(b)-solve(a-1));
    }
    return 0;
}

容斥原理(principle of inclusion-exclusion)：令 \(X\) 为一个有限集合，\(P_1, P_2,\dots , P_m\) 是一些性质的集合，对于任意 \(S \subseteq [m]\) ，即 \(S\subseteq \{1,2,\cdots,m\}\) ，定义 \(N(S) = \{x \in X \mid \forall i \in S : x \text{ has } P_i\}\) 。那么 \(X\) 中满足性质 \(P_{1\sim m}\) 的元素个数为 \[ \sum_{S \subseteq [m]} (-1)^{|S|+1} \left|N(S)\right| \] 如果是不满足任何一个性质的话，把指数中的 \(|S|+1\) 改成 \(|S|\) 即可。

特别地，对于任意的 \(S \subseteq [m]\) ，如果 \(N(S)\) 只和 \(S\) 的大小（即 \(|S|\) ）有关，那么式子可以化简为 \[ \sum_{i=0}^{m} (-1)^{i+1} \binom{m}{i} N(i) \] 其中 \(N(i)\) 表示对于任意满足 \(S \subseteq [m],|S|=i\) 的 \(N(S)\) 值。

如果是不满足任何一个性质的话，把指数中的 \(i+1\) 改成 \(i\) 即可。

容斥原理的常用技巧：

定义一些“坏性质” \(P_1,\dots,P_m\)
找到对于每个 \(S\subseteq [m]\) 计算 \(N(S)\) 的方法
套用容斥原理计算不满足任何一个“坏性质”的元素个数
注意这里求的是不满足任何坏性质，因此用以下公式 \[ \sum_{S \subseteq [m]} (-1)^{|S|} \left|N(S)\right| \]