ZOJ2836 Number Puzzle
? 解题记录 ? ? 杂OJ ? ? 容斥 ?    2018-08-21 11:01:23    597    0    0

Given a list of integers (A1, A2, ..., An), and a positive integer M, please find the number of positive integers that are not greater than M and dividable by any integer from the given list.

Input

 

The input contains several test cases.

For each test case, there are two lines. The first line contains N (1 <= N <= 10) and M (1 <= M <= 200000000), and the second line contains A1, A2, ..., An(1 <= Ai <= 10, for i = 1, 2, ..., N).

Output

For each test case in the input, output the result in a single line.

Sample Input

3 2
2 3 7
3 6
2 3 7

Sample Output

1
4

简单容斥,枚举集合,大小奇数加、偶数减就行了。计算至少能被一些数整除的个数直接用M/LCM就行了。

#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;
int a[15], n, m;
LL ans;
LL gcd(LL a, LL b) {
	return b ? gcd(b, a % b) : a;
}
void GetAns(int step, LL cnt, int rw) {
	if(cnt > m) return;
	if(step == n + 1) {
		ans += (m / cnt) * rw;
		return ;
	}
	GetAns(step + 1, cnt * a[step] / gcd(a[step], cnt), rw * (-1));
	GetAns(step + 1, cnt, rw);
}

int main() {
	while(~scanf("%d%d", &n, &m)) {
		ans = 0;
		for(register int i = 1; i <= n; ++i)
			scanf("%d", &a[i]);
		GetAns(1, 1, 1);
		printf("%d\n", m - ans);
	}
	return 0;
}


上一篇: HDU4135 Co-prime

下一篇: 多项式基础

597 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航