[原创]容斥原理习题
[原创]容斥原理习题
2017-02-11 23:09:40 Tabris_ 阅读数：981
博客爬取于 2020-06-14 22:41:37
以下为正文
版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54989141
练习题目 VJ:https://vjudge.net/contest/77876#overview
HDU 1796 How many integers can you find
HDU 1685 Booksort
这题应该是整错了 不是容斥原理，看题解都是 IDA*搜索
HDU 2204 Eddy's 爱好
HDU 4407 Sum
对于替换的先不管 最后暴力处理即可，
不替换的时候可以分两段处理
分别计算[1,a-1]和[a,b]的 然后相减就好了
处理先对 p 素因子分解，然后容斥原理计算，
HDU 2841 Visible Trees
显然能够知道题目要求的是
满足gcd(x,y)!=1且x<=n且y<=m的数量
由于数据量不大 ，可以枚举 n 值然后计算[1,m]中与 n 不互质的数的个数，然后用 m 减去即可
对于计算[1,m]中与 n 不互质的数的个数，我们还是要用到容斥原理，
ans = +最大公约数因子个数为1的 -最大公约数因子个数为2的+最大公约数因子个数为3的 -最大公约数因子个数为4的....
最大公约数因子个数最大也就是 8 因为 2357111317*19 > 1e6
所以爆搜也不会超时
POJ 3695 Rectangles
乱搞题，首先居然是想到线段树，要不是做专题就陷进去了。
然后想到求多个矩形相交面积的方法搞，因为 n 比较小但(1<< n)远大于 1e5，所以不用预处理出所有情况，只要对待查询的情况容斥原理计算就好。
