容斥原理的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。
以下列举两个例题：
一、
#include <stdio.h> int main() { int T; scanf("%d",&T); while(T--) { int a,b,c; long long m = 1e9; scanf("%d %d %d",&a,&b,&c); long long sum; sum = m/a + m/b + m/c - m/a/b - m/b/c - m/a/c + m/a/b/c; printf("%lld\n",m - sum); } return 0; }
二、
#include<stdio.h> int main() { int n,T,j,w,e,r,t,y,u,i,o,p,q; scanf("%d",&T); int x; for (n=0;n<T;n++){ scanf("%d",&x); scanf("%d %d %d",&j,&w,&e); r = x/j; t = x/w; y = x/e; u = x/(j*w); i = x/(e*w); o = x/(e*j); p = x/(j*w*e); q = r+t+y-2*(u+i+o)+4*p; //q = x/j + x/w + x/e - 2*(x/j/w + x/e/w + x/e/j) + 4*(x/j/w/e); //【ps：可用其中一行注释概括以上式子……】 printf("%d\n",q); } return 0; }
PS：这两个题的共同点都是素数，，emmm，下次见到素数可以联想一下，，毕竟我见的题少……
