HDU 1796 How many integers can you find

HDU 1685 Booksort

这题应该是整错了不是容斥原理,看题解都是IDA*搜索

对于替换的先不管最后暴力处理即可,
不替换的时候可以分两段处理
分别计算[1,a-1]和[a,b]的然后相减就好了
处理先对p素因子分解,然后容斥原理计算,

显然能够知道题目要求的是
满足 $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
所以爆搜也不会超时

乱搞题，首先居然是想到线段树，要不是做专题就陷进去了。

然后想到求多个矩形相交面积的方法搞，因为n比较小但(1<< n)远大于1e5,所以不用预处理出所有情况,只要对待查询的情况容斥原理计算就好.