首页 > 代码库 > hdu 1796
hdu 1796
How many integers can you find
Time Limit: 12000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4473 Accepted Submission(s): 1284
Problem Description
Now you get a number N, and a M-integers set, you should find out how many integers which are small than N, that they can divided exactly by any integers in the set. For example, N=12, and M-integer set is {2,3}, so there is another set {2,3,4,6,8,9,10}, all the integers of the set can be divided exactly by 2 or 3. As a result, you just output the number 7.
Input
There are a lot of cases. For each case, the first line contains two integers N and M. The follow line contains the M integers, and all of them are different from each other. 0<N<2^31,0<M<=10, and the M integer are non-negative and won’t exceed 20.
Output
For each case, output the number.
Sample Input
12 22 3
Sample Output
7
Author
wangye
Source
2008 “Insigma International Cup” Zhejiang Collegiate Programming Contest - Warm Up（4）
Recommend
wangye
http://acm.hdu.edu.cn/showproblem.php?pid=1796#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<cstdlib>#include<string>#include<algorithm>#include<queue>#include<vector>#include<set>using namespace std;#define LL long longLL n,m,a[20],ans;LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}void dfs(LL id,LL flag,LL LCM){LCM=a[id]*LCM/gcd(a[id],LCM);if(flag)ans=ans+n/LCM;elseans=ans-n/LCM;for(LL i=id+1;i<=m;i++)dfs(i,!flag,LCM);}int main(){while(scanf("%lld%lld",&n,&m)!=EOF){ans=0;for(int i=1;i<=m;i++){scanf("%d",&a[i]);if(!a[i])i--,m--;}n--;for(int i=1;i<=m;i++)dfs(i,1,a[i]);printf("%lld\n",ans);}return 0;}
hdu 1796
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。