HDU 1796How many integers can you find(简单容斥定理)
2024-08-24 14:40:04
How many integers can you find
Time Limit: 12000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3315 Accepted Submission(s): 937
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 2
2 3
2 3
Sample Output
7
Author
wangye
Source
题目大意:很简单的题目,直接看意思就懂哈!
解题思路:容斥定理,加奇减偶,开始忘记求lcm了,囧!!而且开始还特判0的情况,题目中说的必须是除以,所以0不是一个解。。。开始竟然以为需要是因子就可以了。想通了之后直接先筛选一次,把0都筛选出去。
AC代码:
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
using namespace std;
__int64 sum;
int n,m;
int a[25];
int b[25];
int visi[25]; __int64 gcd(__int64 m,__int64 n)
{
__int64 tmp;
while(n)
{
tmp=m%n;
m=n;
n=tmp;
}
return m;
} __int64 lcm(__int64 m,__int64 n)
{
return m/gcd(m,n)*n;
} void cal()
{
int flag=0,i;
__int64 t=1;
__int64 ans;
for(i=0;i<m;i++)
{
if(visi[i])
{
flag++; //记录用了多少个数
t=lcm(t,b[i]);
}
}
ans=n/t;
if(n%t==0) ans--;
if(flag&1) sum+=ans; //加奇减偶
else sum-=ans;
} int main()
{
int i,j,p;
while(~scanf("%d%d",&n,&m))
{
sum=0;
for(i=0;i<m;i++)
scanf("%d",&a[i]); int tt=0; //
for(i=0;i<m;i++)
{
if(a[i]) //去掉0
b[tt++]=a[i];
}
m=tt;
p=1<<m; //p表示选取多少个数,组合数的状态
for(i=1;i<p;i++)
{
int tmp=i;
for(j=0;j<m;j++)
{
visi[j]=tmp&1;
tmp>>=1;
}
cal();
}
printf("%I64d\n",sum);
}
return 0;
} /*
12 2
2 3
12 3
2 3 0
12 4
2 3 2 0
*/ //968MS
最新文章
- 用Excel做出比肩任务管理软件的操作技巧
- 【转载】Selenim入门环境的搭建--Java环境下的Java Maven Project
- RHEL7 修改SSH默认端口及修改SELinux运行状态
- 51Nod 1378 夹克老爷的愤怒
- Repeater控件 ---属性(ItemCommand事件)
- python代码学习day03-序列化学习pickle及json
- 【C#】【MySQL】C# 查询数据库语句@Row:=@Row+1
- TaskTracker任务初始化及启动task源码级分析
- PAT1024. Palindromic Number
- wampserver安装后 mysql 所有数据库丢失的解决方案
- 创建oracle 密码文件
- Python学习笔记(五)Python的切片和迭代
- [Windows Phone]AnimationHelper管理分散的Storyboard
- ssh否password登陆server
- FreeMarker标签
- Android进阶:四、RxJava2 源码解析 1
- JAVA项目从运维部署到项目开发(二.ZooKeeper)
- 【js】使用javascript 实现静态网页分页效果
- 使用Thrift让Python和C#可以相互调用
- HTML 转义字符对应表
热门文章
- HDU 1425 sort 【哈希入门】
- Android development tools line_endings hacking
- 深入理解移动web开发之PPI,Pixel,DevicePixelRatio(转)
- ubuntu - chrome 标题栏, 书签乱码 解决
- python - wsgi协议
- LintCode: isSubTree
- 给IT新男的15点建议:苦逼程序员的辛酸反省与总结
- C++ 函数重载与函数匹配
- Android Scrollview 内部组件android:layout_height=";fill_parent";无效的解决办法
- UI篇--Android中3种方法实现back键动作