容斥原理【模板】

本文主要是介绍容斥原理【模板】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

容斥原理：在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

LL Q[100010],factor[110],num;
//Q数组存放的就是右边边各项的因子数以及正负情况，factor[]存放对应对象的数目，num为有几个对象
void Divid(LL n)  //n的素因子分解,得到每项素因子的个数
{num = 0;for(LL i = 2; i*i <= n; ++i){if(n%i==0){while(n%i==0)n /= i;factor[num++] = i;}}if(n != 1)factor[num++] = n;
}
LL solve(LL n)  //容斥定理，求
{LL k,t,ans;t = ans = 0;Q[t++] = -1;for(LL i = 0; i < num; ++i){k = t;for(LL j = 0; j < k; ++j)Q[t++] = -1*Q[j]*factor[i];}//A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C//Q数组存放的就是A∪B∪C右边边各项的因子数以及正负情况。for(LL i = 1; i < t; ++i)ans += n/Q[i];//n/Q[i]累加起来就是A∪B∪Creturn ans;
}

这篇关于容斥原理【模板】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---