import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int p[]=new int[20];//存m个质数
for(int i=0;i<m;i++) p[i]=sc.nextInt();
long res=0;//结果
for(int i=1;i<(1<<m);i++){ //遍历每一种状态
long cnt=0,t=1;//
for(int j=0;j<m;j++)//遍历每一位
if(((i>>j)&1)==1) {//看是不是1,是的话就代表值p[j]出现在当前状态
cnt++;//有多少个p[j]值在当前运算公式
t*=p[j];//方便做运算
}
//j循环结束后有一个式子是p[j1] ∩ p[j2] ∩ p[j3]...\
//y总课上说过:
//1~n中能被p1,p2,…,pm中的至少一个数整除的整数有n / p1*p2*p3...个
//所以t的作用就是乘某个数i位置上有1的值,然后n/t就是1-n能被i整除的个数
//因为i循环2^m次,所以每个数都正好组合出现一次,判断每个数的正负cnt%2 和 值n/t的总和就是答案
if(cnt%2!=0) res+=n/t; //如果有奇数个数交集就是+
else res-=n/t; //如果有偶数个数交集就是-
}
System.out.println(res);
}
}
复习代码(二次理解):
直接跳过原理记公式
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int p[] = new int[m];
for(int i = 0; i < m; i ++) p[i] = sc.nextInt();
long res = 0;
for(int i = 1; i < (1<<m); i ++){ // 二进制遍历所有集合的选择, 至少要选1个集合,0个集合无意义但是会导致 res -= n/1
long cnt = 0, t = 1;
for(int j = 0; j < m; j ++){
if(((i >> j) & 1) == 1){
cnt ++;
if(t * p[j] > n){ // 当前方案没有意义, n / t == 0,一直累乘下去会爆long
t = -1;
break;
}
t *= p[j]; // 选择集合的最小公倍数
}
}
if(t != -1){ // 容斥原理
if(cnt % 2 != 0) res += n/t;
else res -= n/t;
}
}
System.out.println(res);
}
}