三十七、数学知识——容斥原理

数学知识——容斥原理"/>

三十七、数学知识——容斥原理

容斥原理算法主要内容

• 一、基本思路
• • 1、概念
  • 2、推导与手写笔记
• 二、例题题解

一、基本思路

1、概念

• 简介：
• • 在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。
• 原理：
• • 如果被计数的事物有A、B、C三类，那么，A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。（A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C）
• 公式：

2、推导与手写笔记

• 举例推导：
  
  
• 容斥原理分析：

二、例题题解

// java题解实现
import java.util.*;public class Main{static int N = 20;static int[] p = new int[N];public static void main(String[] args){Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();for(int i = 0; i < m; i++){p[i] = in.nextInt();}long res = 0;       // 代表可以整除的集合总数个数for(int i = 1; i < 1 << m; i++){    // 遍历过程一共 2^m - 1 项，1 << m代表的是2^m// 表示从 1——2^m - 1个数，也就是这么多种选法，每个数字代表了一种选择方法// 每一位代表了每一个质数是否参与了此次选择，1代表选择进行了组成long t = 1;   // t 为 p1 p2 p3 ... 之间的乘积，为了后面进行 n/(p1*p2*...) 下取整做准备// 为了求解集合中p的倍数元素个数int count = 0;      //表示这个数字中有多少个质数元素构成for(int j = 0; j < m; j++){     // 遍历的是每个数的位运算中的第m位（二进制位数）//我们这里的i是用二进制来表示每一项，二进制的有多少项1就表示这是多少质数项的交集if((i >> j & 1) == 1){count++;t = t * p[j];if(t > n){t = -1;break;}}}if(t != -1){        // 判断 n 中可以有 t 的倍数的个数if(count % 2 == 0){res = res - (long)n/t;      }else{res = res + (long)n/t;}}}System.out.println(res);}
}