C++(g++ 7.5.0) 解法, 执行用时: 95ms, 内存消耗: 432K, 提交时间: 2023-04-26 21:32:31

#include<bits/stdc++.h>
using namespace std;
int prime[25];
int main()
{
	int n,m;cin>>n>>m;
	int sum=0;
	int i,j;
	for(i=0;i<n;i++)
	 cin>>prime[i];
	for(i=1;i<(1<<n);i++)
	{
		int s=0,t=m;
		for(j=0;j<n;j++)
		{
			if(i&(1<<j))
			{
				s++;
				t/=prime[j];
			}
		}
		if(s%2) sum+=t;
		else sum-=t;
	}
	cout<<sum<<endl;
	return 0;
}

C++ 解法, 执行用时: 20ms, 内存消耗: 400K, 提交时间: 2022-05-03 21:19:41

#include<bits/stdc++.h>
using namespace std;
long long n,m,c[100000];
long long k=0;
void dfs(long long a,long long b){
	k+=m/b;
	for(int i=a+1;i<=n;i++){
		dfs(i,-b*c[i]);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>c[i];
	}
	for(int i=1;i<=n;i++){
		dfs(i,c[i]); 
	} 
	cout<<k<<endl;
} 

Python3 解法, 执行用时: 107ms, 内存消耗: 4620K, 提交时间: 2022-03-11 17:23:37

def dfs(cnt,temp,opt):
    global res
    if temp > m:
        return
    if cnt:
        res += m//temp*opt
    for i in range(cnt+1,n+1):
        dfs(i,temp*li[i],-opt)

n,m = map(int,input().split())
li = list(map(int,input().split()))
li.insert(0,0)
res = 0
dfs(0,1,-1)
print(res)