这一道题目主要是要帮助我们养成容斥的思维
容斥主要是从集合的角度思考问题的,而且等式右边是奇加偶减,还是按照集合的大小从小到大依次考虑的
我们这里显然转化成不互质的个数(肯定不能用欧拉函数),于是把\(N\)分解质因数,然后再按照容斥原理考虑
先考虑集合大小为\(1\)的情况:即一个质数的倍数
我们枚举\(i\)加起来
然后考虑集合大小为\(2\)的情况:即两个质数的倍数
我们枚举\(i\)和\(j\)然后减掉就好了
接下来依次类推
标签:质数,容斥,枚举,集合,考虑,hdu4135 From: https://www.cnblogs.com/dingxingdi/p/18018234