//容斥原理，c[i]表示i当前要算的次数，复杂度和第二层循环相关 O(nlogn~n^2) LL in_exclusion(int n,int *c) { for(int i=0;i<=n;i++) c[i]=1; //不一定是这样初始化，要算到的才初始化为1 LL ans=0; for(int i=0;i<=n;i++) if(i要算) { ans+=(统计数)*c[i]; for(int j=i+1;j<=n;j++) if(i会算到j) c[j]-=c[i];//j要算的次数减去算i时已经算了的次数 } return ans; }
容斥原理结论：
1~n中x的倍数有n/x个,因而gcd(a1,a2,...,am)=kx(1<=ai<=n)中的ai都在这n/x个数中，若ai<a(i+1),则可用容斥原理算出gcd(a1,a2,...,am)=x的对数。
也可以用莫比乌斯反演：
当F(n) = sigma{f(d),n|d}，则f(n) = sigma{mu(d/n)*F(d),n|d}
f(x)表示1~n中选m个数gcd=x的个数，则F(x)表示1~n中选m个数的gcd=kx的个数
然后f(n)=sigma{mu(x/n)*F(x),n|x}
题目链接：https://icpc.njust.edu.cn/Problem/Local/1923/
这里容斥原理算出的c[i]和莫比乌斯函数u[i]相等，说明莫比乌斯反演就是一种容斥，
不过是逆思维的容斥,即将问题细分为互斥的最小元，所有最小元的并就是结果
因此，别的容斥也可以将算的过程中需要用到的u[i]一次算出，后面直接利用该数组
如F(n)=sigma{f(x),x和n满足的条件}<==>f(n)=sigma{u(逆条件)*F(x),x和n满足的条件}
这个结论在国家集训队2013论文集中的浅谈容斥原理有提到
1 LL in_exclusion(int x,int n,int *c) 2 { 3 n/=x; 4 for(int i=0;i<=n;i++) c[i]=1; 5 LL ans=0; 6 for(int i=2;i<=n;i++) 7 { 8 ans+=C(n/i,m)*c[i]; 9 for(int j=i<<1;j<=n;j+=i) c[j]-=c[i]; 10 } 11 return C(n/i,m)-ans; 12 }
原文：http://www.cnblogs.com/cdyboke/p/5406221.html
