数学知识

BraumAce2024年7月1日约 6263 字大约 21 分钟

数学知识

1. 质数

1.1 试除法判定质数

从小到大遍历，只判断能否被小于 sqrt(x) 的数整除。

时间复杂度为 O(sqrt(n)).

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0)
            return false;
    return true;
}

1.2 试除法分解质因数

从小到大尝试 n 的所有因数，每个正整数都能够以唯一的方式表示成它的质因数的乘积。

结论：n 中最多只包含一个大于 sqrt(n) 的因子。

反证法证明：如果有两个大于 sqrt(n) 的因子，那么相乘会大于 n。于是我们发现只有一个大于 sqrt(n) 的因子，可以对其进行优化。如果最后 n 还是 >1，说明这就是大于 sqrt(n) 的唯一质因子，输出即可。

时间复杂度为 O(log n) ~ O(sqrt(n)).

void divide(int x)
{
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0)
        {
            int s = 0; //s表示次幂
            while (x % i == 0) 
            {
                x /= i;
                s++;
            }
            cout << i << ' ' << s << endl; //输出i的s次幂
        }
    
    if (x > 1) 
        cout << x << ' ' << 1 << endl;
    cout << endl;
}

汇总

// 假设输入都是正数
// 素数测试 O(√n)
bool is_prime(int n)
{
    for (int i = 2; i <= n / i; i++){
        if (n % i == 0)
            return false;
    }
    return n != 1;
}

// 约数枚举 O(√n)
vector<int> divisor(int n)
{
    vector<int> res;
    for (int i = 1; i <= n / i; i++){
        if (n % i == 0){
            res.push_back(i);
            if (i != n / i) res.push_back(n / i);
        }
    }
    return res;
}

// 整数分解 O(√n)
map<int, int> prime_factor(int n)
{
    map<int, int> res;
    for (int i = 2; i <= n / i; i++){
        while (n % i == 0){
            ++res[i];
            n /= i;
        }
    }
    if (n != 1) res[n] = 1;
    return res;
}

1.3 筛法求素数

1.3.1 朴素筛法（埃氏筛）

从 2 到 n 枚举，（一个数的倍数一定是合数）筛掉它的倍数，如果该数没有被筛掉，那它就是一个质数。

（1）调和级数：当 n 趋于无穷大时，1 + 1/2 + 1/3 + … + 1/n = ln n + C.

（2）对朴素筛法的优化：任何一个合数都能写成几个质数相乘的形式。只需要判断 2 ~ n-1 中的所有质数，只要它不是 n 的约数，那么 n 就是一个质因数。

（3）质数定理：1~n 当中有 n/ln n 个质数。

（4）思路：从小到大枚举所有的质数，然后删去它们的所有的倍数，就删去了所有的合数，剩下的就是质数。

时间复杂度为 O(n ln ln n).

int primes[N], cnt;     // primes[]存储所有素数，cnt记录素数个数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (st[i]) continue;
        primes[cnt++] = i;
        for (int j = i; j <= n; j += i) //用质数把其所有的倍数都筛掉
            st[j] = true;
    }
}

1.3.2 区间筛法

给定整数 $a$ 和 $b$ ，问区间 $[a, b)$ 内有多少个素数。

解法：

因为 $b$ 以内的合数的最小质因数一定不超过 $\sqrt{b}$ ，如果有 $\sqrt{b}$ 以内的素数表的话，就可以把埃氏筛法运用在 $[a, b)$ 上了。

所以先预处理好 $[a, \sqrt{b})$ 和 $[a, b)$ 的素数表，然后从 $[a, \sqrt{b})$ 的表中筛得素数的同时，也将其倍数从 $[a, b)$ 的表中划去，最后剩下的就是区间 $[a, b)$ 内的素数了。

#define ll long long
bool is_primes[N];
bool is_primes2[N];

void get_prime(ll a, ll b)
{
    for (int i = 0; (ll)i * i < b; i++) is_primes2[i] = true;
    for (int i = 0; i < b - a; i++) is_prime[i] = true;
    
    // is_primes[i - a] = true => i是素数
    for (int i = 2; (ll)i * i < b; i++){
        if (is_primes2[i]){
            for (int j = 2 * i; (ll)j * j < b; j += i) is_primes2[j] = true;
            for (ll j = max(2LL, (a + i - 1) / i; j < b; j += i) is_primes[j - a] = false;
        }
    }
}

1.3.3 线性筛（欧拉筛）

核心思路：用最小质因子去筛合数。

当 i % primes[j] != 0 时，
说明此时遍历到的 primes[j] 不是 i 的质因子，只可能是此时 primes[j] 的最小质因子，
所以 primes[j] * i 的最小质因子就是 primes[j].

当有 i % primes[j] == 0 时，
因为我们是从小到大遍历的，说明此时的 prime[j] 是满足条件的第一个数，即找到了 primes[j] 就是 i 的最小质因子，
因此 primes[j] * i 的最小质因子也就是 primes[j]，
之后用 st[primes[j + 1] * i] = true 去筛合数时，就不是用最小质因子去更新了，
所以此时应该退出循环，避免重复筛选。

时间复杂度为 O(k)

int primes[N];     // primes[]存储所有素数
int cnt;           //记录素数个数
bool st[N];        // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) 
            primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++)
        {
            //标记，pj一定是pj*i的最小质因子
            st[primes[j] * i] = true;
            //从小到大遍历，如果 i%pj=0，则pj一定是i的最小公因子
            if (i % primes[j] == 0) break;
        }
    }
}

2. 约数

2.1 试除法求所有约数

从小到大判断，如果当前数能整除目标数，说明这个数是它的一个约数。

vector<int> get_divisors(int x)
{
    vector<int> res;
    
    //从小到大枚举n的所有约数对里面比较小的那一个
    for (int i = 1; i <= x / i; i++)
        if (x % i == 0)
        {
            res.push_back(i);
            
            //特判最中间的数
            if (i != x / i) 
                res.push_back(x / i);
        }
    
    sort(res.begin(), res.end());
    
    return res;
}

2.2 约数个数和约数之和

如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

约数之和

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;

    unordered_map<int, int> primes;

    while (n -- )
    {
        int x;
        cin >> x;

        for (int i = 2; i <= x / i; i ++ )
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }

        if (x > 1) primes[x] ++ ;
    }

    LL res = 1;
    for (auto p : primes)
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        while (b -- ) t = (t * a + 1) % mod;
        res = res * t % mod;
    }

    cout << res << endl;

    return 0;
}

2.3 最大公约数与最小公倍数

欧几里得算法（辗转相除法)：

每次都让较大的数对较小数取模，可以缩小问题规模而保持最大公约数不变，然后重复(递归)这个步骤。递归边界使某数变成了0，而此时另一个数即为所求答案.

最坏情况下的时间复杂度为 O(log max(x, y))。

对于大多数情况，辗转相除法时间可以忽略不计。

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

用两数之积除以他们的最大公约数可得最小公倍数：

int lcm(int a, int b)
{
    return a * gcd(a, b) / b; //注意乘除的先后顺序，防止溢出
}

3. 欧拉函数

3.1 求欧拉函数

欧拉函数的定义

1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。
若在算数基本定理中， $N = p_1^{a_1} p_2^{a_2} ... p_m^{a_m}$ ，则：
$ϕ(N) = N × \frac{p_1−1}{p_1} × \frac{p_2−1}{p_2} × … × \frac{p_m−1}{p_m}$

//求x的欧拉函数
int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i++) //分解质因数
        if (x % i == 0)
        {
            res = res / i * (i - 1); //用上面的公式定义求，先整除再乘
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

思路：质数 $i$ 的欧拉函数即为 phi[i] = i - 1： $1$ ~ $i−1$ 均与 $i$ 互质，共 $i−1$ 个。
phi[primes[j] * i] 分为两种情况：
① i % primes[j] == 0 时：primes[j] 是 i 的最小质因子，也是 primes[j] * i 的最小质因子，因此 1 - 1 / primes[j] 这一项在 phi[i] 中计算过了，只需将基数 $N$ 修正为 primes[j] 倍，最终结果为 phi[i] * primes[j] 。
② i % primes[j] != 0：primes[j] 不是 $i$ 的质因子，只是 primes[j] * i 的最小质因子，因此不仅需要将基数 $N$ 修正为 primes[j] 倍，还需要补上 1 - 1 / primes[j] 这一项，因此最终结果 phi[i] * (primes[j] - 1) 。

int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

4. 快速幂

基本思路：

预处理出 $a^{2^0}, a^{2^1}, a^{2^2}, ..., a^{2^{logk}}$ 这 k 个数
将 $a^b$ 用 $a^{2^0}, a^{2^1}, a^{2^2}, ..., a^{2^{logk}}$ 这 k 个数来组合，即组合成 $a^b = a^{2^{x_1}} × a^{2^{x_2}} × ... × a^{2^{x_t}} = a^{2^{x_1} + 2^{x_2} + ... + 2^{x_t}}$
即用二进制来表示

k&1 就是判断 k 的二进制表示中第 0 位上的数是否为 1，若为 1，则为 true，反之为 false.

k&1 也可以用来判断奇数和偶数，b&1 = true 时为奇数，b&1 = false 时为偶数。

求 a^k mod p，时间复杂度为 O(logk)

int qmi(int a, int k, int p)
{
    int res = 1 % p;
    while (k)
    {
        if (k&1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

5. 扩展欧几里得算法

裴蜀定理

若 a, b 是整数,且 gcd(a,b) = d ，那么对于任意的整数 x, y, ax+by 都一定是 d 的倍数。特别地，一定存在整数 x, y，使 ax + by = d 成立。
它的一个重要推论是：
a, b 互质的充分必要条件是存在整数 x, y 使 ax + by = 1 .

用于求解方程 $ax + by = gcd(a, b)$ 的解

当 $b = 0$ 时， $ax + by = a$ 所以有 $x = 1, y = 0$

当 $b \ne 0$ 时，因为 $gcd(a, b) = gcd(b, a % b) $

所以 $x = y', y = x' - [a/b] * y'$

求整数 $x$ 和 $y$ 使得 $ax + by = 1$

如果 $gcd(a, b) \ne 1$ ，显然无解。反之，若 $gcd(a, b) = 1$ ，则可以通过扩展欧几里得来求解。

事实上，一定存在整数对 $(x, y)$ 使得 $ax + by = gcd(a, b)$ .

// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;
}

6. 中国剩余定理

给定 $2n$ 个整数 $a_1, a_2, ... , a_n$ 和 $m_1, m_2, ..., m_n$ ，求一个最小的非负整数 $x$ ，满足 $∀i ∈ [1, n], x ≡ m_i(mod \ a_i)$ .

输入格式

第 1 行包含整数 n。

第 $2 ... n + 1$ 行：每 $i + 1$ 行包含两个整数 $a_i$ 和 $m_i$ ，数之间用空格隔开。

输出格式

输出最小非负整数 x ，如果 x 不存在，则输出 -1.

如果存在 x ，则数据保证 x 一定在 64 位整数范围内。

思路

对于每两个式子，将其等价转换
用扩展欧几里得算法找出一组解
并且判断是否有解
找到最小整数解
等效替代

相当于是每次考虑合并两个式子，将这 n 个式子合并 n - 1 次后变为一个式子。最后剩下的式子就满足我们的答案。

#include <iostream>
#include <algorithm>
#define ll long long 
using namespace std;

//扩展欧几里得
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    
    return d;
}

//可能为负数，取模加模再取模
ll inline mod(ll a, ll b)
{
    return ((a % b) + b) % b;
}

int main()
{
    ll n;
    scanf("%lld", &n);
    
    ll a1, m1;
    scanf("%lld%lld", &a1, &m1);
    
    for (ll i = 1; i < n; i++)
    {
        ll a2, m2, k1, k2;
        scanf("%lld%lld", &a2, &m2);
        
        ll d = exgcd(a1, -a2, k1, k2);
        if ((m2 - m1) % d)
        {
            puts("-1");
            return 0;
        }
        
        k1 = k1 * (m2 - m1) / d;
        k1 = mod(k1, abs(a2 / d));
        m1 = m1 + k1 * a1;
        a1 = abs(a1 / d * a2);
    }
    
    printf("%lld\n", m1);
    
    return 0;
}

7. 高斯消元

给定一个包含 n 个方程 n 个未知数的线性方程组。方程组中的系数为实数。

要求求解这个方程组。

（线性代数方法解非齐次线性方程组）

前置知识：初等行（列）变换

把某一行乘一个非00的数 (方程的两边同时乘上一个非00数不改变方程的解)
交换某两行 (交换两个方程的位置)
把某行的若干倍加到另一行上去（把一个方程的若干倍加到另一个方程上去）

高斯消元适用解法

通过初等行变换把增广矩阵化为阶梯型矩阵并回代得到方程的解
适用于求解包含 n 个方程，n 个未知数的多元线性方程组

算法步骤

枚举每一列c,

找到当前列绝对值最大的一行
用初等行变换(2) 把这一行换到最上面（未确定阶梯型的行，并不是第一行）
用初等行变换(1) 将该行的第一个数变成 11 （其余所有的数字依次跟着变化）
用初等行变换(3) 将下面所有行的当且列的值变成 0

时间复杂度为 O(n^3)

const int eps = 1e-6; //控制精度，小于eps视为0
int a[N][N]; // a[N][N]是增广矩阵

int gauss()
{
    int r, c; //行row,列col
    for (r = 0, c = 0; c < n; c ++ )
    {
        int t = r;
        // 找到绝对值最大的行
        for (int i = r; i < n; i ++ )   
            if (abs(a[i][c]) > abs(a[t][c]))
                t = i;

        if (abs(a[t][c]) < eps) continue;

        // 将绝对值最大的行换到最顶端
        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);
        
        // 将当前行的首位变成1
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];
        
        // 用当前行将下面所有的列消成0
        for (int i = r + 1; i < n; i ++ )       
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;
    }

    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)
                return 2; // 无解
        return 1; // 有无穷多组解
    }

    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];

    return 0; // 有唯一解
}

8. 求组合数

8.1 递推法求组合数

适用题型：

给定两个正整数 a 与 b ，求 $C_a^b \ mod(1e9 + 7)$

递推式：

$C_a ^ b = C_{a - 1} ^ {b - 1} + C_{a - 1} ^ {b}$

// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i++)
    for (int j = 0; j <= i; j++)
        if (!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

8.2 通过预处理逆元的方式求组和数

用 infact(a!) 表示 a! 的逆元

$C_a^b = \frac{a!}{b!\ * \ (a - b)!} = a! \ * \ infact(b!) \ * \ infact((a - b)!)$

快速幂求逆元

费马小定理：如果 $p$ 是一个质数，而整数 $a$ 不是 $p$ 的倍数，则有 $a^{p - 1} ≡ 1\ (mod\ p)$ .

乘法逆元的定义

若整数 b, m 互质，并且对于任意的整数 a，如果满足 b | a，则存在一个整数 x，使得 a / b ≡ a * x (mod m) ，则称 x 为 b 的模 m 乘法逆元，记为 $b^{-1} (mod\ m)$ .
b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时， $b^{m - 2}$ 即为 b 的乘法逆元。

结论：当 b 与 m 互质时，b 的乘法逆元为 $b^{m - 2}$ .

当 b 为 m 的倍数时，b 的逆元不存在。 $b\ *\ x\ \% \ m == 0$ ，b 乘任意一个 x % m 一定等于 0.

首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
如果取模的数是质数，可以用费马小定理求逆元
int qmi(int a, int k, int p)    // 快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}

8.3 卢卡斯(Lucas)定理求组合数

给定 n 组询问，每组询问给定三个整数 a,b,p，其中 p 是质数，请你输出 $C_a^b \ mod \ p$ 的值。

$Lucas$ 定理： $C_a^b ≡ C_{a \% p} ^{b \% p} \ * \ C_{\frac{a}{p}} ^{\frac{b}{p}} \ (mod\ p)$
$C_b^a = \frac{a!}{(a−b!)∗b!} = \frac{a∗(a−1)∗(a−2)∗…∗(a−b+1)∗(a−b)∗…∗1}{(a−b)∗(a−b−1)∗…∗1∗b!} = \frac{a∗(a−1)∗(a−2)∗…(a−b+1)}{b!}$

因此可以递推的每次乘 a 然后除以 b ，因为从 a 到 a - b + 1，所以是乘 b 次。

若p是质数，则对于任意整数 1 <= m <= n，有：
C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)

int qmi(int a, int k, int p)  // 快速幂模板
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int C(int a, int b, int p)  // 通过定理求组合数C(a, b)
{
    if (a < b) return 0;

    LL x = 1, y = 1;  // x是分子，y是分母
    for (int i = a, j = 1; j <= b; i --, j ++ )
    {
        x = (LL)x * i % p;
        y = (LL)y * j % p;
    }

    return x * (LL)qmi(y, p - 2, p) % p;
}

int lucas(LL a, LL b, int p)
{
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

int main()
{
    int n;
    cin >> n;
    
    while (n--)
    {
        ll a, b, p;
        cin >> a >> b >> p;
        
        cout << lucas(a, b, p) << endl;
    }
    
    return 0;
}

8.4 分解质因数法求组合数

输入 a, b，求 $C_a^b$ 的值。

方法：对阶乘分解质因数之后，用高精度相乘即可。

步骤：

筛素数
求每个质数的次数
用高精度乘法把所有质因子乘上

当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
    1. 筛法求出范围内的所有质数
    2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...
    3. 用高精度乘法将所有质因子相乘

int primes[N], cnt;     // 存储所有质数
int sum[N];     // 存储每个质数的次数
bool st[N];     // 存储每个数是否已被筛掉


void get_primes(int n)      // 线性筛法求素数
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}


int get(int n, int p)       // 求n!中的次数
{
    int res = 0;
    while (n)
    {
        res += n / p;
        n /= p;
    }
    return res;
}


vector<int> mul(vector<int> a, int b)       // 高精度乘低精度模板
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ )
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }

    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }

    return c;
}

get_primes(a);  // 预处理范围内的所有质数

for (int i = 0; i < cnt; i ++ )     // 求每个质因数的次数
{
    int p = primes[i];
    sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}

vector<int> res;
res.push_back(1);

for (int i = 0; i < cnt; i ++ )     // 用高精度乘法将所有质因子相乘
    for (int j = 0; j < sum[i]; j ++ )
        res = mul(res, primes[i]);

8.5 卡特兰数

给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的序列的数量为： Cat(n) = C(2n, n) / (n + 1)

9. 容斥原理

给定一个整数 n 和 m 个不同的质数 $p_1, p_2, ..., p_m$ .

请你求出 1 ~ n 中能被 $p_1, p_2, ..., p_m$ 中至少一个数整除的整数有多少个。

记 $S_i$ 为 1 ~ n 中能整除 $p_i$ 的集合，根据容斥原理，所有数的个数为各个集合的并集，计算公式如下

#include<iostream>
using namespace std;
#define ll long long

const int N = 20;
int p[N], n, m;

int main() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) cin >> p[i];

    int res = 0;
    //枚举从1 到 1111...(m个1)的每一个集合状态, (至少选中一个集合)
    for(int i = 1; i < 1 << m; i++) {
        int t = 1;      //选中集合对应质数的乘积
        int s = 0;      //选中的集合数量

        //枚举当前状态的每一位
        for(int j = 0; j < m; j++){
            //选中一个集合
            if(i >> j & 1){
                //乘积大于n, 则n/t = 0, 跳出这轮循环
                if((LL)t * p[j] > n){    
                    t = -1;
                    break;
                }
                s++;          //有一个1，集合数量+1
                t *= p[j];
            }
        }

        if(t != -1)
        {
            if (s % 2)  //选中奇数个集合, 则系数应该是1, n/t为当前这种状态的集合数量
                res += n / t;
            else        //反之则为 -1
                res -= n / t;
        }                  
    }

    cout << res << endl;
    return 0;
}

10. 博弈论

10.1 NIM游戏

必胜状态和必败状态

必胜状态，先手进行__某一个操作__，留给后手是一个必败状态时，对于先手来说是一个必胜状态。即__先手可以走到某一个必败状态__。
必败状态，先手__无论如何操作__，留给后手都是一个必胜状态时，对于先手来说是一个必败状态。即__先手走不到任何一个必败状态__。

给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。

我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。
所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。
NIM博弈不存在平局，只有先手必胜和先手必败两种情况。

定理： NIM博弈先手必胜，当且仅当 a1 ^ a2 ^ … ^ an != 0

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    
    int res = 0;
    while (n--)
    {
        int x;
        cin >> x;
        res ^= x;  //每次异或操作
    }
    
    if (res) puts("Yes");
    else puts("No");
    
    return 0;
}

10.2 公平组合游戏ICG

若一个游戏满足：

由两名玩家交替行动；
在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
不能行动的玩家判负；

则称该游戏为一个公平组合游戏。

NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件 2 和条件 3 。

有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0。
有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。

数学知识

数学知识

1. 质数

1.1 试除法判定质数

1.2 试除法分解质因数

汇总

1.3 筛法求素数

1.3.1 朴素筛法（埃氏筛）

1.3.2 区间筛法

1.3.3 线性筛（欧拉筛）

2. 约数

2.1 试除法求所有约数

2.2 约数个数和约数之和

2.3 最大公约数与最小公倍数

3. 欧拉函数

3.1 求欧拉函数

3.2 筛法求欧拉函数

4. 快速幂

5. 扩展欧几里得算法

裴蜀定理

6. 中国剩余定理

7. 高斯消元

8. 求组合数

8.1 递推法求组合数

8.2 通过预处理逆元的方式求组和数

8.3 卢卡斯(Lucas)定理求组合数

8.4 分解质因数法求组合数

8.5 卡特兰数

9. 容斥原理

10. 博弈论

10.1 NIM游戏

10.2 公平组合游戏ICG

10.3 有向图游戏

10.4 Mex运算

10.5 SG游戏

10.6 有向图游戏的和