数论之容斥原理与经典例题

╰+哭是因爲堅強的太久メ 2022-12-02 13:41 63阅读 0赞

#### 容斥原理 ####

容斥原理是对多个集合的一种**计数方法**。人们为了不重复、不遗漏地计数，想到了一个特别的计数方法，称为容斥原理。

简单来说，某个事物有很多类，我们现在要计算**A、B、C三类的和**，那么**总和**=A类元素个数+B类元素个数+C类元素个数-既是A又是B类元素个数-既是B又是C类元素个数-既是A又是C类元素个数+既是A又是B又是C类元素个数。  
这样计算非常方便且不重不漏，我们用一个集合图直观的就能看出这个原理：  
![容斥原理][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70_pic_center]  
普遍推广：要计算几个并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的大小，然后加回所有三个集合相交的大小，然后再减去四个集合相交的大小… 直到计算到所有集合相交的时候。最终得到的就是我们要的答案了。

--------------------

#### 经典例题 ####

例1：[nc15079 大水题][nc15079]

##### 题目描述 #####

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70_pic_center 1]

--------------------

##### 思路 #####

正如题名，这是一个裸的基础容斥原理的题目。我们要计算不是2 5 11 13倍数的个数时，先计算出是其倍数的个数，再用总数一减。那么此时，我们就用容斥原理来计算是2 5 11 13倍数的个数和，我们先计算是**单个数倍数**的个数，再减去**同时是两个数的倍数**的个数，再加上**同时是三个数的倍数**的个数，再减去**同时是四个数的倍数**的个数即可。

我们在计算是2的倍数的个数时直接用 n/2 就是其倍数的个数，其他也同理。

--------------------

##### 代码解析 #####

#include<iostream>
    using namespace std;
    typedef long long ll;
    
    ll cnt,n;
    
    int main()
    { 
    	while(cin >> n)
    	{ 
    		cnt = n/2 + n/5 + n/11 + n/13;	//是单个数的倍数个数
    		cnt -= n/10 + n/ 22 + n/26 + n/55 + n/65 + n/143;	//减去同时是两个数的倍数的个数
    		cnt += n/110 + n/130 + n/286 + n/715;	//加上同时是三个数的倍数的个数
    		cnt -= n/1430;	//减去同时是四个数的倍数的个数
    		cout << n-cnt << endl;	//输出总数-cnt
    	}
    
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/0ada6966b4cd4c27aac7508f5b154790.png
[nc15079]: https://ac.nowcoder.com/acm/problem/15079
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/c86278d45b2e451d84e320951def3368.png