Nguyên lý bù trừ mở rộng

#include <bits/stdc++.h>
#define ll long long
using namespace std;

template <class T> T gcd (T a, T b) {  while (b) { T r = a % b; a = b; b = r; } return a; }
template <class T> T lcm (T a, T b) { return a / gcd (a, b) * b; }

//long long sum=0;
//long long  num;

ll solve(vector<long long> & v, ll n){
int N=v.size();
ll sum=0;
ll num=n;
for(int i=1;i<(1<<N);i++){
    ll ct=1;
    for(int k=0;k<N;k++)if( i & (1<<k) ) ct=lcm(ct,v[k]);
        if(1 & __builtin_popcount(i))sum+=num/ct;
            else sum-=num/ct;
        }
        return sum;
    }

int main(){
    vector<long long> v;
    ll n,P,x;
   /* cin>>num;
    solve(v);
    ll res=gcd(sum,num);
    cout<<sum/res<<' '<<num/res;
    return 0;*/
    int t;
    cin>>t;
    while(t--){
       cin>>n>>P;
//       sum=0;
       for(int i=0;i<P;i++) {cin>>x ; v.push_back(x);}
       ll res=solve(v,n);
      // ll res=gcd(sum,n);
       cout<<res<<'\n';
       v.clear();
    }
    }