能被整除的数

题目描述

给定一个整数 nn 和 mm 个不同的质数 p1p1, p2p2,…, pmpm。

请你求出 11 ～ nn 中能被 p1p1, p2p2,…, pmpm 中的至少一个数整除的整数有多少个。

算法

容斥原理

记 11 ~ nn 所有数的集合为 AA。设性质 PiPi 为：nn 可以被质数 pipi整除。设 11 ~ nn 中满足性质 PiPi 的数所在的集合为 AiAi，集合大小记为 |Ai||Ai|。至少满足 P1P1, P2P2, …, PmPm 这些性质中至少一个性质的数所在集合显然为

A1∪A2∪…∪Am

A1∪A2∪…∪Am

，则由容斥原理，这个集合的大小为：

|A1∪A2∪…∪Am|=∑i=1m|Ai|−∑1~m 的2组合|Ai∩Aj|+∑1~m 的3组合|Ai∩Aj∩Ak|+…+(−1)m−1|A1∩A2∩…∩Am|

|A1∪A2∪…∪Am|=∑i=1m|Ai|−∑1~m 的2组合|Ai∩Aj|+∑1~m 的3组合|Ai∩Aj∩Ak|+…+(−1)m−1|A1∩A2∩…∩Am|

对于本题，如果一个数满足多个性质，即可以同时被 pi1,pi2,…,pikpi1,pi2,…,pik整除，则这样的数共有

⌊npi1pi2…pik⌋

⌊npi1pi2…pik⌋

个。因此，问题就回到了给定 mm 个质数构成的集合 { p1p1, p2p2,…, pmpm }，这个集合的所有非空子集。

深度优先搜索实现集合非空子集枚举

将这 mm 个数放入数组 pp 中，下标范围为 00 ~ m−1m−1，则问题转化为枚举集合 { 0,1,…,m−10,1,…,m−1 } 所有的非空子集。参考 AcWing 842. 排列数字 ，本题也可以用深度优先搜索。但与排列数字那道题不同的是，一串数字的多个排列有可能对应于一个子集。例如：1 2 3 4 5 和 1 3 2 5 4这两个排列对应于同一个子集 {1,2,3,4,51,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,…,xkx1,x2,…,xk，其中 x1<x2<…<xkx1<x2<…<xk。在第一个数的搜索我们会遍历所有的数，因此 x1x1 一定会被搜到，因此序列中的 x1x1 可以被搜到。假设 x1,x2,…,xi−1x1,x2,…,xi−1可以这个序列可以成功搜索，由于 xi>xi−1xi>xi−1，因此xixi也可以被搜到，所以序列 x1,x2,…,xi−1,xix1,x2,…,xi−1,xi一定会被搜到。因此归纳可得，任意一个组合序列都能被搜索到。

对于每次的搜索，我们需要直到上一级的乘积结果 times，即 pi1pi2…pik−1pi1pi2…pik−1。那么，对于本次搜索到的pikpik，直接乘上之前的乘积，得到新的乘积 new_times，便可算出容斥原理中的新的项 n/(pi1pi2…pik−1)n/(pi1pi2…pik−1)，并据此修改结果变量 res. 但是，应该是加还是减呢？因此，我们还要从上一层接受操作数 op（等于+1或-1）。如果上一层操作数是op，那么传到这层的一定是 -op。这样，结果变量就被修改为 res += op * n / new_times

C++ 代码

/**
• 本质是组合枚举问题，详见自己写的题解
*/
#include
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

}

求乘法逆元

定义:即已知 bb 与 mm 互质 且 b|ab|a 则求一个xx 使得 a/b≡a∗xmodma/b≡a∗xmodm

[注] 简单定义 即 b∗x≡1modmb∗x≡1modm 且 bb 与 mm 互质 则 xx 为 bb 的逆元

1. 当mm为质数时
   求解过程如下 ：

由费马小定理可知

bm−1≡1modm

bm−1≡1modm

而

a/b≡a∗xmodm

a/b≡a∗xmodm

联立以上两式，得:

a/b∗bm−1≡a∗xmodm

a/b∗bm−1≡a∗xmodm

即为

a∗bm−2≡a∗xmodm

a∗bm−2≡a∗xmodm

而b|ab|a,且bb与m互质,因此对于bb来说,一定存在一个aa也与mm互质,故而aa可以在两边同时约去(感谢yxc大佬)

因此

x≡bm−2modm

x≡bm−2modm

无解条件 即 bb与mm不互质时无解,而mm为质数,所以bb只能为mm的倍数，此时无解,也就是b%m0b%m0

2.当m不是质数时,则需要用扩展欧几里得求逆元

3.逆元的作用

当 a,ba,b 很大时 求 a/bmodpa/bmodp 的值

而 a/bmodp≠((amodp)/(bmodp))modpa/bmodp≠((amodp)/(bmodp))modp

因此可以借助逆元转化为乘法,再算,设b的逆元为b−1b−1

则 a/bmodp=a∗b−1modp=((amodp)∗(b−1modp))modpa/bmodp=a∗b−1modp=((amodp)∗(b−1modp))modp

当m为质数时，求解逆元的C++代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int qmi(int a, int b, int p){//快速幂
int res = 1%p;
while(b){
if(b&1) res = (LL)resa%p;
a = (LL)aa%p;
b>>=1;
}
return res;
}
int main(){
int n,a,p;
cin>>n;
while(n–){
cin>>a>>p;//p是质数 求 a的逆元(mod p意义下)
if(a%p) cout<<qmi(a,p-2,p)<<endl;
else cout<<“impossible”<<endl;
}
return 0