传送门

__debug神仙计数课件凑系数入门题，我又被锤了。

我们先不考虑奇数的限制，想一下怎么做。是不是可以将任意子集的lcm进行容斥，算是比较简单的容斥了。

然后我们思考一下，如何通过凑系数来满足奇数的限制。

打表/画韦恩图可知系数为\((-2)^{n-1}\)，暂时还不会推系数的方法，先坑着。

#include<cstdio>
#define ll long long
int t,n,m,a[20];ll ans;
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
void dfs(int num,ll lcm,int cnt){
    lcm=1LL*lcm*a[num]/gcd(lcm,a[num]);
    if(lcm>n)return ;
    if(cnt&1)ans+=1LL*n/lcm*(1<<(cnt-1));
    else ans-=1LL*n/lcm*(1<<(cnt-1));
    for(int i=num+1;i<=m;i++)dfs(i,lcm,cnt+1);
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);ans=0;
        for(int i=1;i<=m;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=m;i++)
            dfs(i,a[i],1);
        printf("%lld\n",ans);
    }
}