首页 > 其他分享 >hdu4135

hdu4135

时间:2024-02-17 19:11:07浏览次数:23  
标签:质数 容斥 枚举 集合 考虑 hdu4135

这一道题目主要是要帮助我们养成容斥的思维

容斥主要是从集合的角度思考问题的,而且等式右边是奇加偶减,还是按照集合的大小从小到大依次考虑的

我们这里显然转化成不互质的个数(肯定不能用欧拉函数),于是把\(N\)分解质因数,然后再按照容斥原理考虑

先考虑集合大小为\(1\)的情况:即一个质数的倍数

我们枚举\(i\)加起来

然后考虑集合大小为\(2\)的情况:即两个质数的倍数

我们枚举\(i\)和\(j\)然后减掉就好了

接下来依次类推

标签:质数,容斥,枚举,集合,考虑,hdu4135
From: https://www.cnblogs.com/dingxingdi/p/18018234

相关文章

  • hdu4135
    求[a,b]中与n互素的数字个数  #include<iostream>#include<algorithm>usingnamespacestd;constintN=200;#defineintlonglonginttot,fac[N];......