How many integers can you find(容斥原理) - HDU 1796

看这题之前先复习一下容斥原理,不然肯定看不懂,呃,如果第一次接触容斥原理的题,可能弄懂了容斥原理你还是看不懂代码,是的,等会你就知道了。

容斥原理简介:在计数时,为了使重叠部分不被重复计算,人们研究出一种新的计数方法:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数方法称为容斥原理

两个集合的容斥原理:

n(A∪B)=n(A)+n(B) -n(A∩B)

要计算几个集合并集的大小,我们要先将所有单个集合的大小计算出来,然后去所有个集合相交的部分,再回所有个集合相交的部分,再去所有个集合相交的部分,依此类推,一直计算到所有集合相交的部分。

也就是加上奇数的数量,减去偶数的数量。

原理还是很好理解的,做题的时候因为有位运算的优化,就需要多思考。

Problem Description

Now you get a number N, and a M-integers set, you should find out how many integers which are small than N, that they can divided exactly by any integers in the set. For example, N=12, and M-integer set is {2,3}, so there is another set {2,3,4,6,8,9,10}, all the integers of the set can be divided exactly by 2 or 3. As a result, you just output the number 7.

给你一个数字N,以及一个有M个整数的数组集合S,求出小于数字N的所有整数集合R,使得集合R中的这些数能被S中的数整除。

比如N=12,集合S是{2, 3},那么还有一个集合R{2, 3, 4, 6, 8, 9, 10},所有整数都能被2或者3整除。输出R的元素个数。

Input

There are a lot of cases. For each case, the first line contains two integers N and M. The follow line contains the M integers, and all of them are different from each other. 0<N<2^31,0<M<=10, and the M integer are non-negative and won’t exceed 20.

多个测试用例,第一行包含数字N和集合S的元素个数M。接着输入集合S的M个数字。N用长整型。

Output

For each case, output the number.

Sample Input

12 2

2 3

Sample Output

7

解题思路:

1、对于数字N,用M中的每个数去整除,然后计算数量,肯定有重复的。

2、通过容斥原理,可以知道n(A∪B∪C...)=n(A)+n(B)+n(C)...-n(A∩B)-n(A∩C)-n(B∩C)...+n(A∩B∩C)...

其中A、B、C表示集合S中的M个数依次整除N所能得到的集合。

对于n(A∩B∩...),只需要取得最小公倍数整除N得到集合。

3、本题性能优化主要有3处

一个是在一开始就去掉不需要重复计算的数字,比如N为12的时候,如果M个数是{2,3,4},首先可以把4去掉,因为能被4整除的肯定能被2整除。

一个是没有用递归。

一个是用到了位运算。位运算这个比较难理解,看代码注释慢慢研究吧,另外可以设置一些打印语句查看整个运行过程,做其他题目也一样,便于理解前后因果。

4、注释比代码还多,与前面那个组合的问题有点相似,数学题目就是这样,难以理解,代码精简,解题的性能差距比较大。

源代码:G++ 78ms HDU排名93

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<fstream>
using namespace std;

long long N;
long long s[100];
vector<long long > q;

//求最大公约数
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

long long solve(int size)
{
    long long ans = 0;
    //将符合条件的m个数,看作m位,每位是0或者是1,那么一共有2^m种状态
    //1<<x就是2的x次方,如1<<0是2的0次方,1<<1是2的1次方
    for (long long i = 1; i < (1 << size); i++)
    {
        long long p = 1;
        int cnt = 0;
        for (long long j = 0; j < size; j++)
        {
            //与操作确定该数字是否参与组合
            //比如这里的size为3,那么二进制(1<<size)-1表示为111
            //i的值用二进制表示依次为1,10,11,100,101,110,111
            //1<<j的值依次为1,10,100
            //如果i的值为110,则1<<j在10和100的时候&i就能大于0
            if ((1 << j)&i)
            {
                //计算最小公倍数
                //lcm(a,b) = a*b/gcd(a,b)
                p = p / gcd(p, q[j]) * q[j];
                cnt++;
            }
        }
        //cnt表示组合有几个数,奇数次减去,偶数次加上
        //这里为啥是(n-1)/p,比如(n-1)=11,p=2,那么被2分的数字肯定是(n-1)/p
        //依次为2、4、6、8、10
        if (cnt & 1)
            ans += (N - 1) / p;
        else
            ans -= (N - 1) / p;
    }

    return ans;
}

//可以将测试数据放在文件里面,便于调试
//fstream ifs("test.txt");
//#define cin ifs

int main()
{
    int M = 0;
    //输入N和M
    while (cin >> N >> M)
    {
        q.clear();
        int flag = 0;
        //输入M个数的集合S
        for (int i = 0; i < M; i++)
        {
            cin >> s[i];
        }
        //排序
        sort(s, s + M);
        //去掉重复的数,比如2和6,去掉6,注意这一步去重非常影响性能
        for (int i = 0; i < M; i++)
        {
            if (s[i] <= 0)
                continue;

            for (int j = i + 1; j < M; j++)
            {
                //是否能够被整除,能够被整除说明不需要参与组合计算
                //比如2和6,能被6整除的肯定能被2整除
                if (s[j] % s[i] == 0)
                    s[j] = -1;
            }
            q.push_back(s[i]);
        }
        long long ans = solve(q.size());
        cout << ans << endl;
    }

    return 0;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-04-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python爬虫与算法进阶

学点算法之字符串的乱序检查

问题 字符串的乱序检查。 一个字符串是另一个字符串的乱序。如果第二个字符串只是第一个的重新排列,例如,’heart’ 和 ‘earth’ 就是乱序字符串。’py...

41580
来自专栏阿凯的Excel

Python读书笔记19(函数与返回值)

为什么计算机与程序可以简化我们的工作量,因为我们只需要了解输入输出即可,不需要关心中间的计算过程。 那我们今天就聊一下如何使用函数输出返回值。 我们设想有一个函...

30460
来自专栏PHP在线

PHP 排序算法实现讲解

所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序 算法在很多领域得到相...

30250
来自专栏林德熙的博客

不使用数据结构反转栈

昨天有人问我一道题,我有一个栈,我不使用其他数据结构,不使用另一个栈,把这个栈里所有数据反转。

8010
来自专栏人工智能头条

写算法,用 C++ 还是用 Java ,差别大吗?

今天带来的文章,是 GitChat 签约作者王晓华在不断被读者吐槽:“好好一本算法书为什么要用 C++ 来写” 时,万般无奈下憋出来的。

32920
来自专栏PPV课数据科学社区

【学习】视觉直观感受 7 种常用排序算法

10月14日发布《统计世界的十大算法》后,很多朋友在后台询问,哪里有“视觉直观感受 7 种常用排序算法”,今天分享给大家,感谢todayx.org。 1. 快速...

32550
来自专栏大数据文摘

视觉直观感受 7 种常用排序算法

20850
来自专栏云霄雨霁

排序算法总结

13800
来自专栏web前端教室

javascript 红皮高程(17)-- 按位异或(XOR)

不吐槽了,继续研究JS,今天是按位异或这个操作符,它用符号(^)表示,它也是有二个操作数,这二个数当然也是十进制转成二进制之后的数。 它的规则就是,二个数的数值...

23060
来自专栏北京马哥教育

看完这篇,你就知道Python生成器是什么

生成器是 Python 初级开发者最难理解的概念之一,虽被认为是 Python 编程中的高级技能,但在各种项目中可以随处见到生成器的身影,你得不得去理解它、使用...

386120

扫码关注云+社区

领取腾讯云代金券