题目描述
给定一个整数 n 和 m 个不同的质数 p1, p2,…, pm。
请你求出 1 ~ n 中能被 p1, p2,…, pm 中的至少一个数整除的整数有多少个。
算法
容斥原理
记 1 ~ n 所有数的集合为 A。设性质 Pi 为:n 可以被质数 pi整除。设 1 ~ n 中满足性质 Pi 的数所在的集合为 Ai,集合大小记为 |Ai|。至少满足 P1, P2, …, Pm 这些性质中至少一个性质的数所在集合显然为
A1∪A2∪…∪Am,则由容斥原理,这个集合的大小为:|A1∪A2∪…∪Am|=m∑i=1|Ai|−∑1~m 的2组合|Ai∩Aj|+∑1~m 的3组合|Ai∩Aj∩Ak|+…+(−1)m−1|A1∩A2∩…∩Am|
对于本题,如果一个数满足多个性质,即可以同时被 pi1,pi2,…,pik整除,则这样的数共有 ⌊npi1pi2…pik⌋ 个。因此,问题就回到了给定 m 个质数构成的集合 { p1, p2,…, pm },这个集合的所有非空子集。
深度优先搜索实现集合非空子集枚举
将这 m 个数放入数组 p 中,下标范围为 0 ~ m−1,则问题转化为枚举集合 { 0,1,…,m−1 } 所有的非空子集。参考 AcWing 842. 排列数字 ,本题也可以用深度优先搜索。但与排列数字那道题不同的是,一串数字的多个排列有可能对应于一个子集。例如:1 2 3 4 5 和 1 3 2 5 4这两个排列对应于同一个子集 {1,2,3,4,5}。因此,为了避免深度优先搜索的时候出现重复搜索的情况,我们规定搜索的序列必须是单调递增的,即后面搜索到的数必须比前面的数大,这样就能避免因数字的排列引起的重复。例如,在之前的搜索我们得到的结果是 0 1 3 4,那么现在搜索的数的范围(即第 5 个数)必须从 5 开始,排列为 0 1 3 4 5 或 0 1 3 4 6 或 0 1 3 4 7 等等。
下面用归纳法证明上述算法的正确性。对于一个组合序列 x1,x2,…,xk,其中 x1<x2<…<xk。在第一个数的搜索我们会遍历所有的数,因此 x1 一定会被搜到,因此序列中的 x1 可以被搜到。假设 x1,x2,…,xi−1可以这个序列可以成功搜索,由于 xi>xi−1,因此xi也可以被搜到,所以序列 x1,x2,…,xi−1,xi一定会被搜到。因此归纳可得,任意一个组合序列都能被搜索到。
对于每次的搜索,我们需要直到上一级的乘积结果 times
,即 pi1pi2…pik−1。那么,对于本次搜索到的pik,直接乘上之前的乘积,得到新的乘积 new_times
,便可算出容斥原理中的新的项 n/(pi1pi2…pik−1),并据此修改结果变量 res
. 但是,应该是加还是减呢?因此,我们还要从上一层接受操作数 op
(等于+1或-1)。如果上一层操作数是op,那么传到这层的一定是 -op
。这样,结果变量就被修改为 res += op * n / new_times
C++ 代码
/**
* 本质是组合枚举问题,详见自己写的题解
*/
#include <iostream>
using namespace std;
typedef long long LL;
const int M = 20;
int n, m;
int p[M];
/**
* s: 当前允许搜索的最小下标
* times: 前面的质数乘积。注意times变量的类型要取成long long,因为乘积有可能溢出
* op: 操作数,取+1或-1
* res: 保存最终结果的变量,由于此变量被引用,因此可以实时被修改
*/
void dfs(int s, LL times, int op, int &res) {
for (int i = s; i < m; i++) {
LL new_times = times * p[i]; // 前面的乘积结果乘上这个质数的到新的乘积
res += op * (n / new_times); // 将新的项加到结果上
dfs(i + 1, new_times, -op, res); // 之后的数从i+1开始搜索,传递乘上pi后的新乘积,并将op取反
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) scanf("%d", p + i);
int res = 0;
dfs(0, 1, 1, res);
printf("%d", res);
return 0;
}
这个好像过不了了大佬
我觉得应该是因为new_times超过LL了,再判断一下就过了。
void dfs(int s, LL times, int op, int &res) {
for (int i = s; i < m; i++) {
LL new_times = times * p[i]; // 前面的乘积结果乘上这个质数的到新的乘积
if(new_times<=n)
{
res += op * (n / new_times); // 将新的项加到结果上
dfs(i + 1, new_times, -op, res); // 之后的数从i+1开始搜索,传递乘上pi后的新乘积,并将op取反
}
}
orz