站外题求条

问题描述

有 m m个质数： p1,p2,...,pm p1,p2,...,pm。（可能有相同）

请你求出 1−n 1−n中有多少个数字 x x满足： x x至少是其中一个质数的倍数。输入描述

第一行两个正整数 n,m n,m含义如描述。（ 1≤n≤109 1≤n≤109， 1≤m≤16 1≤m≤16）

接下来一行 m m个质数 p1,p2,...,pm p1,p2,...,pm。（ 2≤pi≤109 2≤pi≤109）输出描述

在一行中输出满足条件的数字个数。样例输入

10 2

2 3 样例输出

7 提示说明

满足条件的数字有：2 3 4 6 8 9 10，共 7 个。

41 pts:

CPP

#include <iostream>
//#include <iomanip>
#include <algorithm>
//#include <cmath>
//#include <climits>
//#include <cctype>
//#define int long long
#define fup(c, st, ed, f) for (int (c) = (st); (c) <= (ed); (c) += (f))
#define fdn(c, st, ed, f) for (int (c) = (st); (c) >= (ed); (c) -= (f))
#define FASTIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//#define save(x) fixed << setprecision(x)
using namespace std;
using ll = long long;
const int MAXN = 20;

int n, m, p[MAXN], ans;

signed main()
{
	cin >> n >> m;
	for (int i = 0; i < m; ++i) cin >> p[i];
	sort(p, p + m);
	int size = unique(p, p + m) - p;
	for (int i = 1; i < (1 << size); ++i)
	{
		int cnt = 0, lcmm = 1;
		for (int j = 0; j < size; ++j)
		{
			if ((1 << j) & i)
			{
				++cnt;
				lcmm *= p[j];
			}
		}
		if (cnt & 1) ans += n / lcmm;
		else ans -= n / lcmm;
	}
	cout << ans;
	return 0;
}

可以提供一组样例 hack 我。

讨论操作

回复

相关推荐

站外题求条