HDU 4135 Co-prime 详解 容斥原理

1. 题目描述

1.1. Limit

Time Limit: 1000 ms

Memory Limit: 32768 kB

1.2. Problem Description

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.3. Input

The first line on input contains T (0<T≤100) the number of test cases, each of the next $T$T lines contains three integers $A,B,N$A,B,N where $(1\le A\le B\le 10^{15})$(1≤A≤B≤1015) and $(1\le N\le 10^9)$(1≤N≤109).

1.4. Output

For each test case, print the number of integers between A and B inclusive which are relatively prime to N. Follow the output format below.

1.5. Sample Input

2
1 10 2
3 15 5

1.6. Sample Output

Case #1: 5
Case #2: 10

In the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.

1.7. Source

The Third Lebanese Collegiate Programming Contest

2. 解读

这道题我们需要使用到的是容斥原理。

容斥原理分为三种实现¹：

1.位运算与二进制枚举（容易理解）

2.队列数组（耗时最短）

3.递归（代码最短但不容易理解）

在这里我们主要讨论比较好理解的位运算与二进制枚举方法，其他两种方法可以参考深海沧澜夜未央的博客²。

首先分析问题，我们要求的是区间 $[A,B]$[A,B] 之内 和 $N$N 互质的数的个数，考虑道题目中的范围 $1\le A\le B\le 10^{15}$1≤A≤B≤1015，暴力算法是不太可能了。

而在之前的一篇笔记中，我们提到了用埃氏筛法来求 $[2,n]$[2,n] 范围内的所有质数，主要思想是不断筛除 $[2,n]$[2,n] 中的非质数和它的倍数，直到列表内只剩下质数为止。也就是说筛除掉一个区间内的非质数是比较高效的。

顺着这个思路我们就可以想到，我们可以求出区间 $[2,A-1]$[2,A−1] 之内和 $N$N 不互质的数的数量 $w_{A-1}$wA−1​ 和 区间 $[2,B]$[2,B] 之内和 $N$N 不互质的数的数量 $w_B$wB​，计算 $(B - w_B) - (A - 1- w_{A - 1}) $ 就可以求出答案了。

那么，我们要怎么求出 $w_{A-1}$wA−1​ 和 $w_B$wB​呢，不需要一个个去筛除那么麻烦，只需要求出 $N$N 的所有质因数 $p_i$pi​，形成一个集合 $P$P，把 $[2,A-1]$[2,A−1] 和 $[2,B]$[2,B] 中所有 $P$P 的倍数的数量求出来并减去就可以了。

如果 $P$P 集合中只有一个数 $p_1$p1​ ，我们只需要这样计算就可以了

$w_{A-1}=\lfloor \frac{A-1}{p_1}\rfloor$wA−1​=⌊p1​A−1​⌋

$w_B=\lfloor \frac{B}{p_1}\rfloor$wB​=⌊p1​B​⌋

但很明显 $P$P 集合中很可能不仅仅只有一个数，这里就涉及到容斥原理了。

假设 $P=\{2,3,5\}$P={2,3,5}， $A=30$A=30， $B=60$B=60，那么计算公式如下

wA−1​===​⌊2A−1​⌋+⌊3A−1​⌋+⌊5A−1​⌋−⌊2×3A−1​⌋−⌊3×5A−1​⌋−⌊2×5A−1​⌋+⌊2×3×5A−1​⌋14+9+5−4−1−2+021​​

wB​===​⌊2B​⌋+⌊3B​⌋+⌊5B​⌋−⌊2×3B​⌋−⌊3×5B​⌋−⌊2×5B​⌋+⌊2×3×5B​⌋30+20+12−10−4−6+244​​

$ans=(B-w_B)-(A-1-w_{A-1})=8$ans=(B−wB​)−(A−1−wA−1​)=8

这里又涉及到容斥原理中一个奇加偶减的规律，也就是在迭代计算的过程中 $w_B$wB​ 要加上 $B$B 除以奇数个质因数相乘所得的结果，减去 $B$B 除以偶数个质因数相乘所得的结果。

又有问题出现了，我们要怎么遍历所有组合的情况呢？ 在最开始提到的位运算与二进制枚举方法闪亮登场。还是假设 $P=\{2,3,5\}$P={2,3,5}，把 $P$P 的组合情况 $G_p$Gp​ 用 3 位二进制来表示

$G_p=(XXX{)}_B,(X\in \{0,1\})$Gp​=(XXX)B​, (X∈{0,1})

根据排列组合规律， $n$n 个数的任意个数的组合共有 $2^n$2n 种情况。

$\sum _{i=0}^n{C}_n^i=2^n$i=0∑n​Cni​=2n

我们只需要把 $G_p$Gp​ 从 $0$0 加到 $2^n-1$2n−1 即可

$G_p\in \left[\right(000{)}_B,\left(111{)}_B\right]$Gp​∈[(000)B​,(111)B​]

若 $G_p$Gp​ 中某一位置 $j$j 为 1，则把 $P\left[j\right]$P[j] 取出与其他为 1 的质因数相乘即可遍历所有组合情况。

3. 代码

#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;
typedef long long ll;

// 存储质因数
ll prime[100];
// 质因数计数
int cnt;

// 计算质因数
void init(int m)
{
    cnt = 0;
    for (ll i = 2; i * i < m; i++)
        // 若为因数
        if (m % i == 0) {
            //prime储存素因子，cnt为素因子的个数
            prime[cnt++] = i;
            // 将这个质因数从m中除去，防止计算到质因数的倍数
            while (m % i == 0) {
                m /= i;
            }
        }
    //这里是因为有的n的因子大于sqrt(n)，比如14，他的素因子有2，7
    if (m > 1)
        prime[cnt++] = m;
}

// 容斥原理计算[2, cur] 中不与 N 互斥的数的数量
ll IE_Principle(ll cur)
{
    // 存储质因数组合的乘积
    ll res = 0;
    // 存储结果
    ll ans = 0;
    // 从 0 遍历到 2^cnt - 1
    for (ll i = 1; i < ll(1 << cnt); i++) {
        res = 1;
        ll flag = 0;
        // 遍历所有数位
        for (ll j = 0; j < cnt; j++) {
            //出现因子
            if (i & (ll(1 << j))) {
                // 统计出现的集合个数
                flag++;
                // 取并之后的因子乘积
                res *= prime[j];
            }
        }
        // 判断组合中因子个数的奇偶性
        if (flag & 1) {
            // 若为奇数 加
            ans += cur / res;
        } else {
            // 若为偶数 减
            ans -= cur / res;
        }
    }
    return ans;
}
int main()
{
    // test case
    ll t;
    cin >> t;
    // 计数
    int icase = 0;
    // 存储 A B N
    ll a, b, n;
    // 存储结果
    ll ans;
    // 对每一个test case进行遍历
    while (t--) {
        // 初始化
        memset(prime, 0, sizeof(prime));
        // 输入
        cin >> a >> b >> n;
        // 求质因数
        init(n);
        // 使用容斥原理进行计算并输出
        ans = b - IE_Principle(b) - (a - 1 - IE_Principle(a - 1));
        printf("Case #%d: %lld\n", ++icase, ans);
    }
    return 0;
}

代码参考自深海沧澜夜未央的博客²，思路借鉴了生如夏花的博客³。

4. 参考文献

[1] 深海沧澜夜未央. CSDN博客. 容斥原理（组合数学）总结

[2] 深海沧澜夜未央. CSDN博客. HDU4135 Co-prime【容斥原理】3方法

[3] 生如夏花. 博客园博客. hdu 4135(容斥原理)

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。