题目描述

已知 $n$ 个数，求 $1$ ~ $t$ 中有多少个数不是 $n$ 个数中任何一个数的倍数

输入格式

第一行两个整数 $n$ 和 $t$，第二行 $n$ 个整数

这是我用容斥原理写的代码，其中 $num[i]$ 表示由 $i$ 个输入的数据相乘得到的数，但是 WA 了，求大佬帮我看看。原题是上海市计算机学会组办的6月月赛乙组最后一题

#include<bits/stdc++.h>
#define MAXN 30
using namespace std;
typedef long long ll;
ll n, t, ans;
ll a[MAXN];
vector<ll> num[MAXN];
void dfs(ll step, ll sum, ll cnt){
    if(step > n){
        num[cnt].push_back(sum);
        return ;
    }
    dfs(step + 1, sum, cnt);
    dfs(step + 1, sum * a[step], cnt + 1);
}
int main(){
    scanf("%lld%lld",&n,&t);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    dfs(1, 1, 0);
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < num[i].size(); j++){
            if(i % 2 == 1) ans += t / num[i][j];
            else ans -= t / num[i][j];
        }
    }
    printf("%lld\n",t - ans);
    return 0;
}