1#include <iostream>
2#include <vector>
3using namespace std;
4typedef long long ll;
5
6// 求 1~n 中与 m 互素的数的个数
7// 思路：先对 m 质因数分解，然后容斥
8ll coprime_count(ll n, ll m) {
9    // 质因数分解 m
10    vector<ll> primes;
11    ll temp = m;
12    for (ll i = 2; i * i <= temp; i++) {
13        if (temp % i == 0) {
14            primes.push_back(i);
15            while (temp % i == 0) temp /= i;
16        }
17    }
18    if (temp > 1) primes.push_back(temp);
19
20    int k = primes.size();
21    ll result = 0;
22
23    // 枚举所有质因子的子集（用位运算）
24    for (int mask = 1; mask < (1 << k); mask++) {
25        ll prod = 1;   // 当前子集中质因子的乘积
26        int bits = 0;  // 当前子集的大小
27
28        for (int i = 0; i < k; i++) {
29            if (mask & (1 << i)) {
30                prod *= primes[i];
31                bits++;
32            }
33        }
34
35        // 容斥：奇数个质因子取正（减），偶数个取负（加）
36        if (bits % 2 == 1) {
37            result += n / prod;  // 能被 prod 整除的数的个数
38        } else {
39            result -= n / prod;
40        }
41    }
42
43    // 总数 - 能被至少一个质因子整除的数 = 与 m 互素的数
44    return n - result;
45}
46
47int main() {
48    ll n, m;
49    cin >> n >> m;
50    cout << "1~" << n << " 中与 " << m << " 互素的数有 "
51         << coprime_count(n, m) << " 个" << endl;
52    return 0;
53}

1#include <iostream>
2using namespace std;
3typedef long long ll;
4const int MOD = 1e9 + 7;
5
6// 错排数 D(n)：n 个元素的全错位排列数
7// 即没有任何元素在原来位置上的排列数
8// D(n) = n! * Σ(i=0 to n) (-1)^i / i!
9// 递推公式：D(n) = (n-1) * (D(n-1) + D(n-2))
10
11const int MAXN = 1000005;
12ll D[MAXN];
13
14void init_derangement(int n) {
15    D[0] = 1; // 空排列算一种
16    D[1] = 0; // 1个元素无法错排
17    for (int i = 2; i <= n; i++) {
18        D[i] = (ll)(i - 1) % MOD * ((D[i-1] + D[i-2]) % MOD) % MOD;
19    }
20}
21
22int main() {
23    int n;
24    cin >> n;
25    init_derangement(n);
26    cout << "D(" << n << ") = " << D[n] << endl;
27    return 0;
28}

1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5typedef long long ll;
6
7// 求 [1, n] 中能被 a[] 中至少一个数整除的数的个数
8ll count_divisible(ll n, vector<ll>& a) {
9    int k = a.size();
10    ll result = 0;
11
12    for (int mask = 1; mask < (1 << k); mask++) {
13        ll lcm_val = 1;
14        int bits = __builtin_popcount(mask);
15
16        for (int i = 0; i < k; i++) {
17            if (mask & (1 << i)) {
18                // 计算 lcm，防止溢出
19                lcm_val = lcm_val / __gcd(lcm_val, a[i]) * a[i];
20                if (lcm_val > n) break; // 超过 n 则贡献为 0
21            }
22        }
23
24        if (bits % 2 == 1) {
25            result += n / lcm_val;
26        } else {
27            result -= n / lcm_val;
28        }
29    }
30
31    return result;
32}
33
34int main() {
35    ll n;
36    int k;
37    cin >> n >> k;
38    vector<ll> a(k);
39    for (int i = 0; i < k; i++) cin >> a[i];
40
41    cout << "[1, " << n << "] 中能被至少一个数整除的有 "
42         << count_divisible(n, a) << " 个" << endl;
43    return 0;
44}