[玲珑杯1138] 震惊，99%的中国人都会算错的问题

这题果然标题党

题目链接：Portal

Solution

这一题一看m很小，表示可以容斥。

根据容斥原理的基本式子有：
[ |overline{bigcup_{i = 1}^{n} A_i}| =sum f(1)|A_i| + sum f(2)|A_i cup A_j| + dots + sum f(n)|bigcup_{i = 1}^{n}A_i| ]
其中f(n)表示第n项的容斥系数,也就是每个集合会被计数多少次。

可以打表发现这题是(f(n)=(-1)^{n + 1} * 2 ^{n - 1})

Codes

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a),i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i,i##_end_ = (b); i >= i##_end_; --i)
#define clar(a,b) memset((a),(b),sizeof(a))
#define debug(...) fprintf(stderr,__VA_ARGS__)
typedef long long LL;
typedef long double LD;
int read() {
    char ch = getchar();
    int x = 0,flag = 1;
    for (;!isdigit(ch); ch = getchar()) if (ch == ‘-‘) flag *= -1;
    for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x * flag;
}
void write(int x) {
    if (x < 0) putchar(‘-‘),x = -x;
    if (x >= 10) write(x / 10);
    putchar(x % 10 + 48);
}

const int Maxn = 1e9,Maxm = 19,Maxsi = 3e5 + 9;
static int n,m,a[Maxm];
static LL ans;

void init() {
    n = read(),m = read(); ans = 0;
    rep (i,m - 1) a[i] = read();
}

int gcd(int a,int b) {
    return b ? gcd(b,a % b) : a;
}

void solve() {
    rep (i,1,(1 << m) - 1) {
        int cnt = __builtin_popcount(i);    
        LL lcm = 1,flag = 0;
        rep (j,m - 1) 
            if ((i >> j) & 1) {
                lcm = lcm * a[j] / gcd(lcm,a[j]);
                if (lcm > n) {
                    flag = 1;
                    break;
                }
            }
        if (!flag) ans += n / lcm * (((cnt + 1) & 1) ? -1 : 1) * (1 << (cnt - 1));
    }
    cout << ans << endl;
}

int main() {
    freopen("iFrog1138.in","r",stdin);
    freopen("iFrog1138.out","w",stdout);

    int T = read();
    while (T--) {
        init();
        solve();
    }

#ifdef Qrsikno
    debug("nRunning time: %.3lf(s)n",clock() * 1.0 / CLOCKS_PER_SEC);
#endif
    return 0;
}