转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
题目:给出两组数,要求在区间内找出有多少个数,满足至少能被第一组中的一个数整除,而且至少能不被第二组中的一个数整除。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3490
开始题目看错了,以为是不能被第二组中的任何一个数整除,这样应该更难处理了。
我们定义第一个条件为P1,第二个条件为P2。
则要求的是P1&&P2。由于P2条件比较奇怪,至少不能被一个数整除,所以我们考虑其反命题,能被第二组中的所有数整除,则是能被最小公倍数整除。
那么P1&&P2=P1-P1&&(~P2),这样便可以解决了。
我调用的容斥次数太多,太耗时了,可以在一次调用中全部解决。请读者自行思考
另外就是注意溢出神马的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#define LL long long
#define eps 1e-7
using namespace std;
vector<LL>b;
int cbln,cbun;
LL l,r,k;
LL ret,bun;
LL gcd(LL a,LL b){
return b==0?a:gcd(b,a%b);
}
void dfs(int k,int remain,int idx,int cnt,LL num,LL n){
if(remain==0){
if(k&1)
ret+=n/num;
else
ret-=n/num;
return ;
}
if(idx>=cnt)
return ;
dfs(k,remain,idx+1,cnt,num,n);
LL tmp=num/gcd(num,b[idx])*b[idx];
if(tmp<=n&&tmp>0)
dfs(k,remain-1,idx+1,cnt,tmp,n);
}
LL slove(LL up,int cnt,LL init){
if(up<=1) return 0;
ret=0;
for(int i=1;i<=cnt;i++)
dfs(i,i,0,cnt,init,up);
return ret;
}
int main(){
while(scanf("%d%d%lld%lld",&cbln,&cbun,&l,&r)!=EOF){
if(cbln+cbun+l+r==0) break;
b.clear();
for(int i=0;i<cbln;i++){
scanf("%lld",&k);
b.push_back((LL)k);
}
bun=1;
bool flag=false;
LL a=slove(r,cbln,1LL)-slove(l-1,cbln,1LL);
for(int i=0;i<cbun;i++){
scanf("%lld",&k);
if(i==0) bun=k;
else{
bun=bun/gcd(bun,k)*k;
if(bun<0) flag=true;
}
}
if(flag){
printf("%lld\n",a);
continue;
}
LL b=slove(r,cbln,bun)-slove(l-1,cbln,bun);
printf("%lld\n",a-b);
}
return 0;
}
分享到:
相关推荐
zoj 1535 Lucky Ticket.md
zoj 3690 Choosing number.md
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
一个非常非常非常非常实用的zoj结题代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
zoj 1003 c语言的,要写这么多描述吗。。
ZOJ1805代码
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
zoj1027解题指南和代码,还不错,是学校培训给的。
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 题库 详细解答 解题代码 acm
zoj4041正确题解源代码,以及运行程序
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
zoj吐血制作,希望大家喜欢