Skip to content

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 the number of test cases, each of the next lines contains three integers where and .

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：

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

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

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

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

首先分析问题，我们要求的是区间 之内 和 互质的数的个数，考虑道题目中的范围 ，暴力算法是不太可能了。

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

顺着这个思路我们就可以想到，我们可以求出区间 之内和 不互质的数的数量 和 区间 之内和 不互质的数的数量 ，计算 就可以求出答案了。

那么，我们要怎么求出 和 呢，不需要一个个去筛除那么麻烦，只需要求出 的所有质因数 ，形成一个集合 ，把 和 中所有 的倍数的数量求出来并减去就可以了。

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

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

假设 ，，，那么计算公式如下

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

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

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

我们只需要把 从 加到 即可

若 中某一位置 为 1，则把 取出与其他为 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;
}

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

4. 参考文献#

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

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

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

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

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

Back to top