Helping Cicada（LightOJ-1117）

Problem Description

Cicada is an insect with large transparent eyes and well-veined wings similar to the "jar flies". The insects are thought to have evolved 1.8 million years ago during the Pleistocene epoch. There are about 2,500 species of cicada around the world which live in temperate tropical climates.

These are all sucking insects, which pierce plants with their pointy mouthparts and suck out the juices. But there are some predators (like birds, the Cicada Killer Wasp) that attack cicadas. Each of the predators has a periodic cycle of attacking Cicadas. For example, birds attack them every three years; wasps attack them every 2 years. So, if Cicadas come in the 12th year, then birds or wasps can attack them. If they come out in the 7th year then no one will attack them.

So, at first they will choose a number N which represents possible life-time. Then there will be an integer M indicating the total number of predators. The next M integers represent the life-cycle of each predator. The numbers in the range from 1 to N which are not divisible by any of those M life-cycles numbers will be considered for cicada's safe-emerge year. And you want to help them.

Input

Input starts with an integer T (≤ 125), denoting the number of test cases.

Each case contains two integers N (1 ≤ N < 2^31) and M (1 ≤ M ≤ 15). The next line contains M positive integers (fits into 32 bit signed integer) denoting the life cycles of the predators.

Output

For each test case, print the case number and the number of safe-emerge days for cicada.

Sample Input

2
15 3
2 3 5
10 4
2 4 5 7

Sample Output

Case 1: 4
Case 2: 3

题意：t 组数据，每组给出一个数 n 和 m 个数，问从这 m 个数中，1-n 里不能被这 m 个数中任意一个整除的数有多少个

思路：

对于任意一个数 a[i] 来说，我们能知道在 1-n 中有 n/a[i] 个数是 a[i] 的倍数，但这样将 m 个数扫一遍一定会用重复的数，因此需要用到容斥原理

根据容斥定理的奇加偶减，对于 m 个数来说，其中的任意 2、4、...、2k 个数就要减去他们最小公倍数能组成的数，1、3、...、2k+1 个数就要加上他们的最小公倍数，因此 m 个数就有 2^m 种情况，对于每种状态，依次判断由多少种数组成，然后再进行奇加偶减即可

根据容斥原理有：sum=从 m 中选 1 个数得到的倍数的个数-从 m 中选 2 个数得到的倍数的个数 + 从 m 中选 3 个数得到的倍数的个数 - 从 m 中选 4 个数得到的倍数的个数……

那么最后的答案就是 n-sum

Source Program

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 2000+5;
const int dx[] = {0,0,-1,1,-1,-1,1,1};
const int dy[] = {-1,1,0,0,-1,1,-1,1};
using namespace std;

LL GCD(LL a,LL b){
    return !b?a:GCD(b,a%b);
}
LL LCM(LL a,LL b){
    return a/GCD(a,b)*b;
}
LL a[N];
int main(){
    int t;
    scanf("%d",&t);

    int Case=1;
    while(t--){
        LL n;
        int m;
    	scanf("%lld%d",&n,&m);
        for(int i=0;i<m;i++)
            scanf("%lld",&a[i]);

        LL sum=0;
        for(int i=0;i<(1<<m);i++){//2^m种状态
            LL lcm=1;
            LL cnt=0;
            for(int j=0;j<m;j++){
                if(i&(1<<j)){//从m中选出j个数
                    lcm=LCM(lcm,a[j]);
                    cnt++;
                }
            }
            if(cnt!=0){
                if(cnt&1)//奇加
                    sum+=n/lcm;
                else//偶减
                    sum-=n/lcm;
            }
        }

        printf("Case %d: %lld\n",Case++,n-sum);
    }
    return 0;
}