集合中的质数

[编程题]集合中的质数

热度指数：1 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个集合和一个数m。

集合里面有n个质数。

请你求出从 1 到 m 的所有数中，至少能被集合中的一个数整除的数的个数。

输入描述:

第一行两个正整数 n 和 m 。
第二行n个正整数，分别为集合中的质数。

输出描述:

输出一个整数，表示符合要求的正整数的个数。

示例1

输入

3 37
5 7 13

输出

备注:

对于100%的数据，有n<=20，m为有符号64位正整数，集合内质数<=1000000000

算法知识视频讲解

威风镰鼬

发表于 2021-11-25 10:57:03

思路考察容斥定理。质因子最多20个，所以我们可以状压一下，枚举每次选定因子的情况。考虑只有一个因子pri的情况下，1~m个数中总共由m/pri个，那么下一次选定两个因子p1,p2时，就要减去m/(p1*p2)个，加减取决于选定因子的个数。代码 #include<bits/stdc++.h& 展开全文

冰雅

发表于 2022-09-02 10:12:31

题目描述给出一个集合和一个数m。集合里面有n个质数。请你求出从 1 到 m 的所有数中，至少能被集合中的一个数整除的数的个数。思路容斥原理：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复。 1-m的数中展开全文

张广文

发表于 2020-03-23 20:19:38

include<bits/stdc++.h> using namespace std;typedef long long ll;ll m,ans[25],res;int n;void dfs(ll a, int cur,int cnt){ if(a>m) return ; 展开全文

划水_小星

发表于 2020-09-01 08:25:47

题目:https://ac.nowcoder.com/acm/problem/14686思路：运用容斥原理——https://oi-wiki.org/math/inclusion-exclusion-principlezui'h加上dfs直接推算出结果。代码： //#include<bits/ 展开全文