思路

考察容斥定理。质因子最多20个，所以我们可以状压一下，枚举每次选定因子的情况。考虑只有一个因子pri的情况下，1~m个数中总共由m/pri个，那么下一次选定两个因子p1,p2时，就要减去m/(p1*p2)个，加减取决于选定因子的个数。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;

int n,m,pri[21],flag,res,ans=0;

int gcd(int a,int b){return b?a:gcd(b,a%b);}

int lcm(int a,int b){return a*b/gcd(a,b);}

signed main(){
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>pri[i];
	for(int i=1;i<(1<<n);i++){ //枚举子集 
		res=m,flag=0;
		for(int j=0;j<n;j++){
			if((i>>j)&1){
				flag++;
				res/=pri[j]; 
			}
		}
		if(flag&1) ans+=res;
		else ans-=res;
	}
	cout<<ans<<"\n";
	return 0;
}