首页 > 代码库 > SDUT 3023-当N遇上M(容斥原理)
SDUT 3023-当N遇上M(容斥原理)
题目链接:传送门
题意:求[1,n]内与m互质的个数。
容斥原理:奇加偶减(奇数个类的计数和-偶数个类的计数和)
对于这个问题,首先求出m的质因数fac[] , 然后所在区间内有n/fac[i]个数 一定不能与m互质(比如m=8,n=10,对于fac[]=2,有2,4,6,8,10 即5(10/2)个数不能与8互质)。。枚举每一个质因数选还是不选。可以位运算,也可以dfs
第一发容斥,准备系统的刷一下容斥的专题了。。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define maxn 360 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1000000007 #define pp pair<int,int> #define ull unsigned long long #define max(x,y) ( ((x) > (y)) ? (x) : (y) ) #define min(x,y) ( ((x) > (y)) ? (y) : (x) ) using namespace std; ll fac[1111],tot,ans; void div(ll x)//分解质因数 { tot=0; for(ll i=2;i*i<=x;i++) { if(x&&x%i==0) { fac[tot++]=i; while(x&&x%i==0) x/=i; } } if(x>1) fac[tot++]=x; } void dfs(ll num,ll s,ll r,ll n)//n为范围 即(1,n) { if(num==tot) { if(s&1)ans-=n/r;//容斥原理:奇加偶减(那这里为什么还是减?因为n/r是不能和m互质的个数啦) else ans+=n/r; return ; } dfs(num+1,s,r,n); dfs(num+1,s+1,r*fac[num],n); } int main() { ll n,m; while(~scanf("%lld%lld",&n,&m)) { ans=0;div(m); dfs(0,0,1,n); printf("%lld\n",ans); } return 0; }
SDUT 3023-当N遇上M(容斥原理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。