【题目链接】:http://acm.uestc.edu.cn/#/problem/show/1544

【题意】

【题解】



容斥原理题;

1..(2^m)-1枚举

设k为其二进制形式中1的个数;

k为奇数

ans+=2^(k-1)*(n/lcm(对应的k个数))

否则-=…..

如果不加那个系数的话,算的是这几个数的公倍数的个数…



【Number Of WA】



2



【反思】



没有注意到自己做的结果是什么…



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 15;

int n, m;

int a[N + 5];

int two[N + 5];

LL gcd(LL x, LL y) {

    return y == 0 ? x : gcd(y, x%y);

}

LL lcm(LL x, LL y) {

    return (x / gcd(x, y)*y);

}

void solve() {

    cin >> n >> m;

    rep1(i, 1, m)

        cin >> a[i];

    LL ans = 0;

    rep1(i, 1, two[m] - 1) {

        int num = 0; LL temp = 1;

        rep1(j, 1, m)

        if (i&(two[j-1])){

            num++;

            if (temp > n) continue;

            temp = lcm(temp, a[j]);

        }

        if (num & 1)

            ans += two[num-1]*(n / temp);

        else

            ans -= two[num-1]*(n / temp);

    }

    cout << ans << endl;

}

int main() {

    //Open();

    Close();

    two[0] = 1;

    rep1(i, 1, 15) two[i] = two[i - 1] * 2;

    int T;

    cin >> T;

    while (T--) {

        solve();

    }

    return 0;

}