HDU4135 Co-prime 题解

题目链接：HDU4135 Co-prime

题目描述：

给定一个数 \(N\)，请你统计 \(A\) 到 \(B\)（含 \(A\) 和 \(B\)）之间有多少个整数与 \(N\) 互质。

如果两个整数除了 \(1\) 之外没有其他公因数，或者说它们的最大公约数为 \(1\)，就称它们互质。

\(1\) 与任何整数都互质。

输入格式：

第一行包含整数 \(T\)（\(0<T\le 100\)），表示测试用例的数量。接下来的 \(T\) 行，每行包含三个整数 \(A\)、\(B\)、\(N\)，其中 \(1\le A\le B\le 10^{15}\)，且 \(1\le N\le 10^9\)。

输出格式：

对于每组测试用例，输出 \(A\) 到 \(B\)（含两端）之间与 \(N\) 互质的整数个数。请按照下面的格式输出。

首先一个常见转化 \(\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\) 即可。

容斥原理的常用技巧：

  1. 定义一些“坏性质” \(P_1,\dots,P_m\)

  2. 找到对于每个 \(S\subseteq [m]\) 计算 \(N(S)\) 的方法

  3. 套用容斥原理计算不满足任何一个“坏性质”的元素个数

  4. 注意这里求的是不满足任何坏性质，因此用以下公式 \[ \sum_{S \subseteq [m]} (-1)^{|S|} \left|N(S)\right| \]