1、容斥原理。
如果班里有15个人喜欢物理，10个人喜欢英语，16个人喜欢数学，那么班里面有多少个人呢？
10+16+15显然是错的，因为存在一个人既喜欢物理也喜欢英语，那么就把这些重复加的人的数量给剪掉。
也就是减去既喜欢物理又喜欢英语的人，既喜欢英语又喜欢数学的人，既喜欢数学又喜欢物理的人，这样就把刚才多加进去的人全部剪掉了，
可是这样既喜欢英语又喜欢数学又喜欢英语的这么一个人，他在这次剪的过程剪了2次，那么就再把喜欢3个科目的人加起来，这就是容斥原理。
也就是|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|C∩A|+|A∩B∩C|。
2、有重复元素的全排列。
给定k个元素，其中第i个元素有ai个，求全排序个数。
令所有n i 之和为n，再设答案为x。首先做全排列，然后把所有元素编号，其中第s种元素
编号为1～n s （例如，有3个a，两个b，先排列成aabba，然后可以编号为a 1 a 3 b 2 b 1 a 2 ）。这样
做以后，由于编号后所有元素均不相同，方案总数为n的全排列数n!。根据乘法原理，得到
了一个方程：n 1 !n 2 !n 3 !…n k x!=n!，移项即可。
也就是先全部都包括在里面，然后把重复的去除。
3、有重复选择的组合。
杨辉三角
二项式定理。
C(K,N)=K/(N-K+1)C(K-1,N)。可以想想为什么有这个公式。
然后可以根据这个公式递推出C(K,N)。
#include <iostream>
using namespace std;
int main(){
int a,i,j,k,n,m,b[100];
cin>> n;
b[0]=1;
for(i=1;i<=n;i++)
b[i]=b[i-1]*(n-i+1)/i;
for(i=0;i<=n;i++)
cout << b[i] <<" ";
return 0;
}其中n为多少就是杨辉三角的第几+1行。
不难看出，约数的个数意思也就是其各个因子的个数，如对于84=(2^2)*(3^1)*(7^1).
也就是其既可以整除2和整除2^2，3，7。也就是相当与其唯一分解式各个式的指数可以取0、1、2、。。。到a1，84也就是对于2，可以取0、1、2，
对于3，可以取0、1，对于7，可以取0、1。也就是其因子可以由哪些素数组成。
欧拉函数，给定一个N，找出所有n中与n互素的数，也就是这两个数的最大公约数为1。
用容斥原理。首先从总数n中分别减去是p 1 , p 2 , … , p k 的倍数的个数（对于素数p来
说，“与p互素”和“不是p的倍数”等价），即 ，然后加上“同时是两个素因子
的倍数”的个数 ，再减去“同时是3个素因子的倍数”——写成一个“学术
味比较浓”的公式就是：
其可以写为=(1-1/p1)(1-1/p2)(1-1/p3)...的形式。
1、从1开始到n，找到gcd（i，n）==1的那个数，然后打上标记，再把其的倍数打上标记，循环到n，可以筛选出互素数。
#include <iostream>
using namespace std;
bool vis[50000];
int gcd(int a,int b){
//cout << a << "\t" << b <<endl;
return b==0?a:gcd(b,a%b);
}
int main(){
memset(vis,0,sizeof(vis));
int a,i,j,k,n,m,b[100];
cin>> n;
// cout << gcd(n,5) << endl;
for(i=1;i<=n;i++)if(!vis[i]&&gcd(n,i)!=1)
for(j=i;j<=n;j+=i){
vis[j]=1;
// cout << j << endl;
}
int f1=0;
for(i=1;i<=n;i++){
if(!vis[i])
f1++;
}
cout << f1<< endl;
return 0;
}
2、如对84，n=n/i*(i-1)，意思是减去为i倍数的数，