# How many integers can you find

Time Limit: 12000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 6434    Accepted Submission(s): 1849

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```

Sample Output

```7这道题目是给定了因子，而且还不是互质的，所以在容斥原理上，就不能简单想乘，要求最小公倍数LCM另外有可能因子为0#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <math.h>

using namespace std;
typedef long long int LL;
LL gcd(LL a,LL b)
{
return b?gcd(b,a%b):a;
}
LL ans,a[15],n,m;
void dfs(int id,int flag,int lcm)
{
lcm=a[id]/gcd(a[id],lcm)*lcm;
if(flag)
ans+=n/lcm;
else
ans-=n/lcm;
for(int i=id+1;i<m;i++)
dfs(i,!flag,lcm);
}
int main()
{
while(cin>>n>>m)
{
n--;
for(int i=0;i<m;i++)
{
scanf("%d",&a[i]);
if(!a[i]) i--,m--;
}
ans=0;
for(int i=0;i<m;i++)
dfs(i,1,a[i]);
printf("%lld\n",ans);
}
return 0;
}```

0 条评论

## 相关文章

### HDUOJ---3371Connect the Cities

Connect the Cities Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768...

33770

### HDUOJ---Can you solve this equation?

Can you solve this equation? Time Limit: 2000/1000 MS (Java/Others)    Memory Li...

29980

### hdu----(5056)Boring count(贪心)

Boring count Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768...

34450

### hdu 3948 Portal (kusral+离线)

Portal Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Ja...

30460

### HDOJ 1004

Let the Balloon Rise Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 655...

21180

### HDUOJ---1213How Many Tables

How Many Tables Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

34570

### HDUOJ1060Leftmost Digit

Leftmost Digit Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/327...

33380

### hdu 3908 Triple(组合计数、容斥原理)

Triple Time Limit: 5000/3000 MS (Java/Others)    Memory Limit: 125536/65536 K (J...

400100

### HDUOJ----1170Milk

Milk Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java...

286100

### Ignatius and the Princess II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Oth...

15020