首页 > 代码库 > 【P1813】8的倍数
【P1813】8的倍数
容斥原理，居然没想到……要补一下数论了
原题：
小x最近对数字8很感兴趣，有8进制，2008奥运会之类的。
现在小x想知道，在[x,y]区间里，有多少个数能被8整除。
小y觉得题目太简单，于是给出n个其他数，问在[x,y]区间里，有多少个数能被8整除且不能被这n个数整除。
1≤n≤15，1≤x≤y≤10^9，N个数全都小于等于10^4大于等于1。
x-y区间这个问题，可以搞前缀和，求1-(x-1)和1-y，然后减
枚举2^n种 n个因子是否使用 的情况，然后搞8和 当前情况使用因子 的lcm，用x-1或y除这个lcm，得到在这个范围内能被lcm整除的有几个，如果用了奇数个，答案就减，偶数个就加
搞lcm的时候，如果lcm已经大于x-1或y，就不用再往下搞
代码；
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 int gcd(int x,int y){return (y)?gcd(y,x%y):x;} 8 int n,a[20],xx,yy; 9 bool use[20];10 int ansx,ansy,bowl=0;11 void dfs(int x,int y){12 if(x>n){13 long long lcm=8; int ge=0;14 for(int i=1;i<=n;i++)if(use[i]){15 lcm*=a[i]/gcd(lcm,a[i]);16 if(lcm>y) break;17 ge++;18 }19 if(ge%2) bowl-=y/lcm;20 else bowl+=y/lcm;21 return ;22 }23 use[x]=false; dfs(x+1,y);24 use[x]=true; dfs(x+1,y);25 }26 int main(){//freopen("ddd.in","r",stdin);27 memset(use,0,sizeof(use));28 cin>>n;29 for(int i=1;i<=n;i++) cin>>a[i];30 cin>>xx>>yy;31 dfs(1,yy); ansy=bowl; 32 bowl=0;33 dfs(1,xx-1); ansx=bowl;34 cout<<ansy-ansx<<endl;35 return 0;36 }
【P1813】8的倍数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。