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|$