问题:求1~r中有多少个数与n互素。
对于这个问题由容斥原理,我们有3种写法,其实效率差不多。分别是:dfs,队列数组,位运算。
先说说位运算吧:
用二进制1,0来表示第几个素因子是否被用到,如m=3,三个因子是2,3,5,则i=3时二进制是011,表示第2、3个
因子被用到
LL Solve(LL n,LL r){vector<LL> p;for(LL i=2; i*i<=n; i++){if(n%i==0){p.push_back(i);while(n%i==0) n/=i;}}if(n>1)p.push_back(n);LL ans=0;for(LL msk=1; msk<(1<<p.size()); msk++){LL multi=1,bits=0;for(LL i=0; i<p.size(); i++){if(msk&(1<<i)) //判断第几个因子目前被用到{++bits;multi*=p[i];}}LL cur=r/multi;if(bits&1) ans+=cur;else ans-=cur;}return r-ans;}
然后就是dfs的实现:
void Solve(LL n){p.clear();for(LL i=2; i*i<=n; i++){if(n%i==0){p.push_back(i);while(n%i==0) n/=i;}}if(n>1)p.push_back(n);}void dfs(LL k,LL t,LL s,LL n){if(k==p.size()){if(t&1) ans-=n/s;else ans+=n/s;return;}dfs(k+1,t,s,n);dfs(k+1,t+1,s*p[k],n);}//主函数内是:dfs(0,0,1,r);
经典题目:HDU4135,HDU2841,HDU1695,HDU3501
如果觉得《容斥原理应用(求1~r中有多少个数与n互素)》对你有帮助,请点赞、收藏,并留下你的观点哦!