NC15079 - 大水题

题意

给出一个数, 求到中，有多少个数不是的倍数

数据范围

思路

我们定义集合表示到的整数集合

我们定义下列的性质分别为:

表示能被整除 表示能被整除 表示能被整除 表示能被整除

表示集合中满足性质的元素

那么这个题目其实要求的就是:

根据容斥原理可得:

对于的话，因为这些数字都是质数，那么其实就等于

代码

/**
 *    author: andif
 *    created: 28.08.2023 22:49:12
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
const db eps = 1e-9;

// int force(int n) {
//     int ret = 0;
//     rep(i, 1, n + 1) {
//         if (i % 2 == 0) continue;
//         if (i % 5 == 0) continue;
//         if (i % 11 == 0) continue;
//         if (i % 13 == 0) continue;
//         ret++;
//     }
//     return ret;
// }

int main() {
    // qc;
    ll n;
    while(cin >> n) {
        ll ans = n;
        vi a{2, 5, 11, 13};
        rep(i, 1, (1 << 4)) {
            int x = __builtin_popcount(i) & 1 ? -1 : 1;
            int fm = 1;
            rep(j, 0, 4) {
                if (i & (1 << j)) {
                    fm *= a[j];
                }
            }
            ans = ans + 1ll * x * n / fm;
        }
        // dd(force(n)), de(ans);
        cout << ans << '\n';
    }
    return 0;
}