Inclusion-Exclusion Principle

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute derangements D(n) = n! * sum_{k=0}^{n} (-1)^k / k!  (mod MOD)
5
// We precompute factorials and inverse factorials to get 1/k! quickly.
6
7
static const long long MOD = 1'000'000'007LL;
8
9
long long mod_pow(long long a, long long e) {
10
    long long r = 1 % MOD;
11
    a %= MOD;
12
    while (e > 0) {
13
        if (e & 1) r = (r * a) % MOD;
14
        a = (a * a) % MOD;
15
        e >>= 1;
16
    }
17
    return r;
18
}
19
20
int main() {
21
    ios::sync_with_stdio(false);
22
    cin.tie(nullptr);
23
24
    int n; 
25
    if (!(cin >> n)) return 0;
26
27
    // Precompute factorials and inverse factorials up to n
28
    vector<long long> fact(n + 1), invfact(n + 1);
29
    fact[0] = 1;
30
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i % MOD;
31
    invfact[n] = mod_pow(fact[n], MOD - 2); // Fermat's little theorem (MOD is prime)
32
    for (int i = n; i >= 1; --i) invfact[i - 1] = invfact[i] * i % MOD;
33
34
    // sum_{k=0}^{n} (-1)^k / k!
35
    long long sum = 0;
36
    for (int k = 0; k <= n; ++k) {
37
        long long term = invfact[k]; // 1/k!
38
        if (k % 2 == 1) term = (MOD - term) % MOD; // multiply by (-1)^k
39
        sum += term;
40
        if (sum >= MOD) sum -= MOD;
41
    }
42
43
    long long Dn = fact[n] * sum % MOD;
44
    cout << Dn << '\n';
45
    return 0;
46
}
47

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// onto(m -> n) = sum_{k=0}^{n} (-1)^k * C(n, k) * (n - k)^m (mod MOD)
5
// We precompute factorials for binomial coefficients and use fast exponentiation for powers.
6
7
static const long long MOD = 1'000'000'007LL;
8
9
long long mod_pow(long long a, long long e) {
10
    long long r = 1 % MOD;
11
    a %= MOD;
12
    while (e > 0) {
13
        if (e & 1) r = (r * a) % MOD;
14
        a = (a * a) % MOD;
15
        e >>= 1;
16
    }
17
    return r;
18
}
19
20
int main() {
21
    ios::sync_with_stdio(false);
22
    cin.tie(nullptr);
23
24
    long long m; int n; // m can be large, n typically smaller
25
    if (!(cin >> m >> n)) return 0;
26
27
    // Edge cases
28
    if (n == 0) { cout << (m == 0 ? 1 : 0) << '\n'; return 0; }
29
    if (m < n) { cout << 0 << '\n'; return 0; } // cannot be onto if fewer elements in domain
30
31
    vector<long long> fact(n + 1), invfact(n + 1);
32
    fact[0] = 1;
33
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i % MOD;
34
    auto inv = [&](long long x){ return mod_pow(x, MOD - 2); };
35
    invfact[n] = inv(fact[n]);
36
    for (int i = n; i >= 1; --i) invfact[i - 1] = invfact[i] * i % MOD;
37
38
    auto C = [&](int N, int K)->long long{
39
        if (K < 0 || K > N) return 0;
40
        return fact[N] * invfact[K] % MOD * invfact[N - K] % MOD;
41
    };
42
43
    long long ans = 0;
44
    for (int k = 0; k <= n; ++k) {
45
        long long ways_miss_k = mod_pow(n - k, m); // (n-k)^m
46
        long long comb = C(n, k);
47
        long long term = comb * ways_miss_k % MOD;
48
        if (k % 2 == 1) term = (MOD - term) % MOD; // multiply by (-1)^k
49
        ans += term;
50
        if (ans >= MOD) ans -= MOD;
51
    }
52
53
    cout << ans % MOD << '\n';
54
    return 0;
55
}
56

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Count numbers x in [1..N] with gcd(x, m) = 1.
5
// Inclusion-exclusion over distinct prime factors p1,...,pk of m:
6
// not_coprime = sum_{empty != S subset of primes} (-1)^{|S|+1} floor(N / prod(S))
7
// answer = N - not_coprime.
8
9
int main() {
10
    ios::sync_with_stdio(false);
11
    cin.tie(nullptr);
12
13
    unsigned long long N, m;
14
    if (!(cin >> N >> m)) return 0;
15
16
    // Factor m into distinct primes
17
    vector<unsigned long long> primes;
18
    unsigned long long x = m;
19
    for (unsigned long long p = 2; p * p <= x; ++p) {
20
        if (x % p == 0) {
21
            primes.push_back(p);
22
            while (x % p == 0) x /= p; // remove all powers; only distinct primes matter
23
        }
24
    }
25
    if (x > 1) primes.push_back(x);
26
27
    int k = (int)primes.size();
28
    unsigned long long not_coprime = 0ULL;
29
30
    // Enumerate all non-empty subsets of primes
31
    for (int mask = 1; mask < (1 << k); ++mask) {
32
        // Compute product of selected primes with overflow-safe check
33
        __uint128_t prod128 = 1; // use 128-bit to avoid overflow when multiplying
34
        int bits = __builtin_popcount((unsigned)mask);
35
        for (int i = 0; i < k; ++i) {
36
            if (mask & (1 << i)) {
37
                prod128 *= primes[i];
38
                if (prod128 > N) break; // no contribution if product exceeds N
39
            }
40
        }
41
        if (prod128 == 0 || prod128 > N) continue;
42
        unsigned long long prod = (unsigned long long)prod128;
43
        unsigned long long cnt = N / prod; // multiples of prod in [1..N]
44
        if (bits % 2 == 1) not_coprime += cnt; // add for odd subset size
45
        else not_coprime -= cnt;              // subtract for even subset size
46
    }
47
48
    unsigned long long coprime = N - not_coprime;
49
    cout << coprime << '\n';
50
    return 0;
51
}
52