4）数学知识

文章目录

• 试除法判定质数
• 分解质因数
• 素数筛
• • 欧拉筛法（朴素筛法）
  • 线性筛法
• 试除法求约数
• 约数个数
• 约数之和
• 最大公约数
• 欧拉函数
• • 欧拉函数
  • 筛法求欧拉函数
• 欧拉定理
• 快速幂
• 快速幂求逆元
• 扩展欧几里得算法
• • 扩展欧几里得算法
  • 线性同余方程
• 中国剩余定理
• • 表达整数的奇怪方式
• 高斯消元
• • 高斯消元解线性方程组
  • 高斯消元解异或线性方程组
• 求组合数
• • 求组合数 I
  • 求组合数 II
  • 求组合数 III
  • 求组合数 IV
  • 满足条件的01序列（卡特兰数）
• 容斥原理
• • 能被整除的数
• 博弈论
• • Nim游戏
  • 台阶-Nim游戏
  • 集合-Nim游戏
  • 拆分-Nim游戏

---

试除法判定质数

#include

using namespace std;

int 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;
}

int main(){
    
    scanf("%d", &n);
    
    int x;
    while(n--){
        
        scanf("%d", &x);
        if(is_prime(x)) puts("Yes");
        else puts("No");
    }
    
    return 0;
}

分解质因数

#include
#include

using namespace std;

void divide(int x){
    
    for(int i = 2; i <= x / i; i++){
        
        if(x % i == 0){
            int s = 0;
            while(x % i == 0) x /= i, s++;
            cout << i << ' ' << s << endl;
        }
    }
    if(x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

int main(){
    
    int n;
    cin >> n;
    while(n--){
        
        int x;
        cin >> x;
        divide(x);
    }
    
    return 0;
}

素数筛 欧拉筛法（朴素筛法）

#include
#include

using namespace std;

const int N = 1000010;

int primes[N], cnt;
bool st[N];

void get_primes(int n){
    
    for(int i = 2; i <= n; i++){
        
        if(st[i]) continue;
        primes[cnt++] = i;
        for(int j = i + i; j <= n; j += i){
            st[j] = true;
        }
    }
}

int main(){
    
    int n;
    
    cin >> n;
    
    get_primes(n);
    
    cout << cnt << endl;
    
    return 0;
}

线性筛法

#include 
#include 

using namespace std;

const int N = 1000010;

int primes[N], cnt;
bool st[N];

void get_primes(int n){
    
    for (int i = 2; i <= n; i ++ ){
        
        // 如果当前数没被筛掉,肯定是素数
        if (!st[i]) primes[cnt++] = i;
        
        // 枚举质数中 x * i <= n 的数
        // 对x的i倍的数进行筛取
        for(int j = 0; primes[j] <= n / i; j++){
            
            st[primes[j] * i] = true;
            
            // 如果 x 是 i的最小质因子，它肯定也是x * i的最小质因子
            if(i % primes[j] == 0) break;
        }
    }
}

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

    get_primes(n);

    cout << cnt << endl;

    return 0;
}

试除法求约数

#include
#include
#include

using namespace std;

vector<int> get_divisors(int x){
    
    vector<int> res;
    
    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;
}

int main(){
    
    int n;
    cin >> n;
    
    while(n--){
        
        int x;
        cin >> x;
        
        auto res = get_divisors(x);
        
        for(auto x: res) cout << x << ' ';
        
        cout << endl;
    }
    
    return 0;
}

约数个数

// x 的质因数是p1^a1*p2^a2* ... *pn^an
// x的约数一定满足p1^(0~a1)*p2^(0~a2)*...*pn^(0~an)
// 所以约数的个数为: (a1 + 1) * (a2 + 1) * (a3 + 1) *...* (an + 1)
#include
#include
#include
#include

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) res = res * (p.second + 1) % mod;
    
    cout << res << endl;
    
    return 0;
}

约数之和

// x 的质因数是p1^a1*p2^a2* ... *pn^an
// x的约数一定满足p1^(0~a1)*p2^(0~a2)*...*pn^(0~an)
// 所以约数的个数为: (a1 + 1) * (a2 + 1) * (a3 + 1) *...* (an + 1)
#include
#include
#include
#include

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) res = res * (p.second + 1) % mod;
    
    cout << res << endl;
    
    return 0;
}

最大公约数

#include

using namespace std;

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

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

欧拉函数

欧拉函数

// 欧拉函数：φ(n) (1 ~ n 中与n互质的数的个数)
// 对N分解质因数后：
// N = p1^a1 * p2^a2 ....pk^ak
// φ(N) = N * (1 - 1/p1) * (1 - 1/p2) *...*(1 - 1/pk)
// 例：φ(6) = 6 * (1 - 1/2) * (1 - 1/3) = 2
// 用公式求奥拉函数的时间复杂度是O(n*sqrt(ai)) // 分解质因数求解

#include

using namespace std;


int main(){
    
    int n;
    
    cin >> n;
    
    while(n--){
        
        int a;
        cin >> a;
        
        int res = a;
        for(int i = 2; i <= a / i; i++){
            if(a % i == 0){
                
                res = res / i * (i - 1);    
            }
            
            while(a % i == 0){
                
                a /= i;
            }
        }
        
        if(a > 1) res = res / a * (a - 1);
        
        cout << res << endl;
    }
    
    return 0;
}

筛法求欧拉函数

#include

using namespace std;

const int N = 1000010;

typedef long long ll;

int n;
int primes[N], cnt, phi[N];
bool st[N];

ll get_eulers(int n){
    
    // 1 ~ 1中与1互质的数只有它自己
    phi[1] = 1;
    
    for(int i = 2; i <= n; i++){
        
        if(!st[i]){
            
            primes[cnt++] = i;
            // 如果一个数是质数, 则1 ~ i-1都与其互质
            phi[i] = i - 1;
        } 
        
        for(int j = 0; primes[j] <= n / i; j++){
            
            st[primes[j] * i] = true;
            
            if(i % primes[j] == 0){
                
                // i % primes[j] == 0时, primes[j] 是 i 的最小的质因子
                // 我们可以发现求 φ(i) 时, 只与它的质因子有关,与质因子的次数无关 
                // 所以求 φ(i) 时, 包含了primes[j] // φ(i) = i * (1 - 1/primes[j])*...*(1 - 1/pk)...
                // 此时: i * primes[j] 这个数的质因子与 i 的质因子是完全相同的
                // 所以φ(i * primes[j]) = primes[j] * φ(i)
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            
            // i * primes[j] != 0时, primes[j] 不是 i 的质因子
            // 所以φ(i) 里面不包含 primes[j], 而 i * primes[j] 比 i 多了一个质因子 primes[j];
            // 所以φ(i * primes[j]) = primes[j] * φ(i) * (1 - 1 / primes[j]) = φ(i) * (primes[j] - 1) 
            phi[i * primes[j]] =  phi[i] * (primes[j] - 1);
        }
    }
    
    ll res = 0;
    for(int i = 1; i <= n; i++) res += phi[i];
    
    return res;
}


int main(){
    
    int n;
    
    cin >> n;
    
    cout << get_eulers(n) << endl; 
    
    return 0;
}

欧拉定理

快速幂

#include

using namespace std;

typedef long long LL;

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

int main(){
    
    int n;
    scanf("%d", &n);
    while(n--){
        
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        printf("%lld\n", qmi(a, b, p));
    }
    
    return 0;
}

快速幂求逆元

#include

using namespace std;

typedef long long LL;

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

int main(){
    
    int n;
    
    cin >> n;
    
    int a, b;
    while(n--){
        
        cin >> a >> b;
        if(a % b == 0) puts("impossible");
        else cout << qmi(a, b - 2, b) << endl;
        
    }
    
    return 0;
}

扩展欧几里得算法

扩展欧几里得算法

#include

using namespace std;


int exgcd(int a, int b, int &x, int &y){
    
    if(!b){
        
        // b = 0
        // ax + by = a; ==> x = 1, y 任意
        
        x = 1;
        y = 0;
        return a;
    }
    
    
    int d = exgcd(b, a % b, y, x);
    
    // a * x + b * y = d  本层
    // b * y + (a % b) * x = d  下一层
    // b * y + (a - b * (a / b)) * x
    // a * x + b * (y - (a / b) * x)
    // a * x + b * y               
    // x = x  y = y - (a / b) * x
    
    y = y - (a / b) * x;
    return d;
}

int main(){
    
    int n;
    
    scanf("%d", &n);
    
    while(n--){
        
        int a, b, x, y;
        scanf("%d%d", &a, &b);
        
        exgcd(a, b, x, y);
        
        printf("%d %d\n", x, y);
    }
}

线性同余方程

#include

using namespace std;

typedef long long LL;

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 = y - a / b * x;
    
    return d;
}

int main(){
    
    int n;
    scanf("%d", &n);
    
    int a, b, m, x, y;
    
    while(n--){
        
        scanf("%d%d%d", &a, &b, &m);
        // ax 三 b (mod m)
        // ax - my = b
        // a = a, b = -m
        // x = x * d, y = y * d
        int d = exgcd(a, -m, x, y);
        
        if(b % d) puts("impossible");
        else printf("%lld\n", (LL)b / d * x % m);
    }
    
    return 0;
}

中国剩余定理

表达整数的奇怪方式

#include

using namespace std;

typedef long long LL;

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;
}

int main(){
    
    int n;
    cin >> n;
    
    n -= 1;
    
    bool flag = true;
    LL a1, m1, a2, m2, k1, k2;
    cin >> a1 >> m1;
    while(n--){
        
        cin >> a2 >> m2;
        
        int d = exgcd(a1, a2, k1, k2);
        if((m2 - m1) % d){
            flag = false;
            break;
        }
        
        k1 *= (m2 - m1) / d;
        LL t = a2 / d;
        k1 = (k1 % t + t) % t;
        m1 = k1 * a1 + m1;
        a1 = abs(a2 / d * a1);
    }
    
    
    if(!flag) puts("-1");
    else{
        
        cout << (m1 % a1 + a1) % a1 << endl;
    }
    
    
    return 0;
}

高斯消元 高斯消元解线性方程组

#include
#include
#include

using namespace std;

const int N = 110;
const double eps = 1e-6;

int n;
double a[N][N];

int gauss(){
    
    // 列, 行
    int c, r;
    
    for(c = 0, r = 0; c < n; c++){
        
        int t = r;
        // 找到第c列中, 绝对值最大的一行
        for(int i = r; i < n; i++){
            
            if(fabs(a[i][c]) > fabs(a[t][c])) t = i;
        }
        
        // 如果当前列的最大值是0,说明r行以下，这列全为0, 则跳过此列
        if(fabs(a[t][c]) < eps) continue;
        
        // 将r, t 行做交换,由于这两行的前c列都为0, 所以前c列不交换
        for(int i = c; i < n + 1; i++) swap(a[t][i], a[r][i]);
        // 将这行(r行)的c列(第一个非0的数), 变为1(等式两边同除以a[r][c])
        for(int i = n; i >= c; i--) a[r][i] /= a[r][c];
        
        // 将r行下面所有行的第c列消为0
        for(int i = r + 1; i < n; i++){
            
            // 如果当前行的c列是非零的
            if(fabs(a[i][c]) > eps){
                
                for(int j = n; j >= c; j--){
                    
                    // 设当前行第c列的值为val
                    // 对当前行的第j列的数减去第r行第j列的val倍
                    // 相当于当前行减去(r行的val倍)
                    a[i][j] -= a[i][c] * a[r][j];
                }
            }
        }
        
        r++;  // 换下一行
    }
    
    // 说明在上面循环的时候, 存在某一列全为0的情况,这样的话,最下面的r ~ n行等式左边是全为0的情况
    // 说明存在无穷多解或无解的情况
    if(r < n) {
        
        // 如果r ~ n 行等式右边存在非0情况,则无解
        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++){
            
            // 相当于将第i行(i + 1 ~ n)的每一列全消为0
            // 因为只要得到解，所以只用对 bi 进行 *** 作，中间的值，可以不用 *** 作，因为不用输出
            a[i][n] -= a[j][n] * a[i][j];
        }
    }
    
    return 0;
}

int main(){
    
    scanf("%d", &n);
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n + 1; j++){
            
            scanf("%lf", &a[i][j]);
        }
    }
    
    int t = gauss();
    
    if(t == 0){
        
        for(int i = 0; i < n; i++){
            
            printf("%.2f\n", a[i][n]);  // 高斯消元完成后,等式最右边的部分就是对应x的解!!!
        }
        
    }
    else if(t == 1) puts("Infinite group solutions");
    else puts("No solution");
    
    return 0;
}

高斯消元解异或线性方程组

/*
异或运算：异或不进位加法
1)消成上三角矩阵 (枚举列)(找当前列的第一个非零行)(交换)(把同列下面行消零)
2)判断是否唯一解
*/
#include

using namespace std;

const int N = 110;

int n;
int a[N][N];

int gauss(){
    
    int r, c;
    for(c = 0, r = 0; c < n; c++){
        
        int t = r;  // 找当前列的首个非0行
        for(int i = r; i < n; i++){
            
            if(a[i][c]){
                
                t = i;
                break;
            }
        }
        
        if(!a[t][c]) continue;  // 当前列没有找到1
    
        for(int i = c; i <= n; i++) swap(a[r][i], a[t][i]);  // 交换r行和t行
        
        for(int i = r + 1; i < n; i++){  // 用r行把下面所有行的当前列消成0
            
            if(a[i][c]){
                
                for(int j = n; j >= c; j--){
                    
                    a[i][j] ^= a[r][j];
                }
            }
        }
        
        r++;
    }
    
    if(r < n){
        
        for(int i = r; i < n; i++){
            
            if(a[i][n]) 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;
}

int main(){
    
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n + 1; j++){
            
            cin >> a[i][j];
        }
    }
    
    int t = gauss();
    
    if(t == 0){
        for(int i = 0; i < n; i++){
            
            cout << a[i][n] << endl;
        }
    }
    else if(t == 1) puts("Multiple sets of solutions");
    else puts("No solution");
    
    return 0;
}

求组合数

给定 n 组询问，每组询问给定两个整数 a ， b a，b a，b，请你输出 C a b C^b_a Cab​ m o d mod mod ( 1 0 9 + 7 ) (10^9+7) (109+7) 的值。

输入格式
第一行包含整数 n n n。

接下来 n n n 行，每行包含一组 a a a 和 b b b。

输出格式
共 n n n 行，每行输出一个询问的解。

求组合数 I

数据范围
1 ≤ n ≤ 10000 , 1 ≤ b ≤ a ≤ 2000 1≤n≤10000, 1≤b≤a≤2000 1≤n≤10000,1≤b≤a≤2000

递推

#include

using namespace std;

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

int c[N][N];

void init(){
    
    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 - 1] + c[i - 1][j]) % mod;
}

int main(){
    
    int n;
    
    init();
    
    scanf("%d", &n);
    
    while(n--){
        
        int a, b;
        
        scanf("%d%d", &a, &b);
        
        printf("%d\n", c[a][b]);
    }
    
    return 0;
}

求组合数 II

数据范围
1 ≤ n ≤ 10000 , 1 ≤ b ≤ a ≤ 1 0 5 1≤n≤10000, 1≤b≤a≤10^5 1≤n≤10000,1≤b≤a≤105

预处理

#include

using namespace std;

typedef long long ll;

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

ll fact[N], infact[N];

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


int main(){
    
    fact[0] = infact[0] = 1;
    
    for(int i = 1; i < N; i++){
        
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
    
    int n;
    scanf("%d", &n);
    while(n--){
        
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", fact[a] * infact[b] % mod * infact[a-b] % mod);
    }
    
    return 0;
}

求组合数 III

1 ≤ n ≤ 20 , 1 ≤ b ≤ a ≤ 1 0 1 8 , 1 ≤ p ≤ 1 0 5 , 1≤n≤20 , \ 1≤b≤a≤10^18,\ 1≤p≤10^5, 1≤n≤20,1≤b≤a≤1018,1≤p≤105,

lucas 定理

#include
#include

using namespace std;

typedef long long ll;

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;
}

int C(int a, int b, int p){
    
    if(b > a) return 0;
    
    int res = 1;
    for(int i = 1, j = a; i <= b; i++, j--){
        
        res = (ll)res * j % p;
        res = (ll)res * qmi(i, p-2, p) % p;
    }
    
    return res;
}


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;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }
    
    return 0;
}

求组合数 IV

求 a ! a! a! 中有多少个 p p p;

如果某个数中有 p k p^k pk，则它在算 p 1 , p 2 , . . . , p k p^1, p^2,...,p^k p1,p2,...,pk 时分别统计了一次，总共加了 k k k 次

注意结果可能很大，需要使用高精度计算。

数据范围
1 ≤ b ≤ a ≤ 5000 1≤b≤a≤5000 1≤b≤a≤5000

#include
#include

using namespace std;

const int N = 5010;

int sum[N];  // 每一个质数的次数

int primes[N], cnt;
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;
        }
    }
}

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;
}

// n的阶乘中包含的质因子p的个数
int get(int n, int p){
    
    int res = 0;
    while(n){
        
        res += n / p;
        n /= p;
    }
    
    return res;
}

int main(){
    
    int a, b;
    
    cin >> a >> b;
    
    // 筛2 ~ a之间的素数
    get_primes(a);
    
    // 遍历每个质数,求每个质数的次数
    for(int i = 0; i < cnt; i++){
        
        int p = primes[i];
        
        // a!中有多少个质数因子p
        // 减去(a-b)!的多少个质数因子p
        // 再减去b!的多少个质数因子p, 就是总个数
        sum[i] = get(a, p) - get(a - b, p) - get(b, p);
        // sum[i]记录了每一个质数因子出现的次数
    }
    
    // 将质数因子乘到一起,就是结果
    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]);
        }
    }
    
    // 输出
    for(int i = res.size() - 1; i >= 0; i--) printf("%d", res[i]);
    
    return 0;
}

满足条件的01序列（卡特兰数）

#include

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

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;
}

int main(){
    
    int n;
    
    cin >> n;
    
    int a = 2 * n, b = n;
    
    ll res = 1;
    for(int i = 1, j = a; i <= b; i++, j--){
        
        res = res * j % mod * qmi(i, mod - 2, mod) % mod;
    }
    
    cout << res * qmi(n + 1, mod - 2, mod) % mod << endl;
    
    return 0;
}

容斥原理 能被整除的数

/*
设 Si代表1~n中能被i整除的数, 假如n = 10

S2: {2, 4, 6, 8, 10}
S3: {3, 6, 9}

|S2∪S3| = |S2 + |S3| - |S2∩S3| = 5 + 3 - 1 = 7

此题相当于求: |Sp1 ∪ Sp2 ∪ Sp3 ∪ ...∪ Spm| 

|Sp|(1~n中p的倍数的个数) = ⌊n / p⌋
|Spi ∩ Spj| = ⌊n / (pi * pj)⌋  // 因为pi和pj都是质数(互质),所以就相当于找能被pi*pj整除的数的个数
|Sp1∩Sp2∩Sp3...∩Spk| = ⌊n/(p1 * o2 * p3 *..*pk)⌋

对每个集合的计算的时间复杂度是O(k) (k次乘法)
总的就是 O(2^m * m)
*/

#include

using namespace std;

typedef long long ll;

const int N = 20;

int p[N];


int main(){
    
    int n, m;
    cin >> n >> m;
    
    for(int i = 0;i < m; i++) cin >> p[i];
    
    int res = 0;
    
    // 最多m个集合相交,有2^m-1种状态
    for(int i = 1; i < (1 << m); i++){
        // 质数的乘积; 2进制中1的个数
        int t = 1, cnt = 0;
        for(int j = 0; j < m; j++){
            
            if(i >> j & 1){
                
                // 选的数的乘积超过n,则此时对答案没有贡献
                if((ll)t * p[j] > n){
                    
                    t = -1;
                    break;
                }
                
                t *= p[j];
                cnt++;
            }
        }
        
        if(t != -1){
            
            if(cnt & 1) res += n / t;
            else res -= n / t;
        }
    }
    
    cout << res << endl;
    
    return 0;
}

博弈论

Nim游戏

#include

using namespace std;

const int N = 100010;

int main(){
    
    int n;
    
    scanf("%d", &n);
    
    int res = 0;
    
    while(n--){
        
        int x;
        scanf("%d", &x);
        res ^= x;
    }
    
    if(res) puts("Yes");
    else puts("No");
    
    return 0;
}

SG 函数：

台阶-Nim游戏

/*
结论：如果开始时奇数台阶上值异或为0，则先手必败，反之必胜
证明：
先手时，如果奇数台阶异或非0，根据Nim游戏，先手总有一种方式使奇数台阶异或为0
于是先手留了奇数台阶异或为0的状态给后手。


轮到后手时：
①当后手移动偶数台阶上的石子时，先手只需要将对手移动的石子继续移动到下一个台阶，
这样奇数台阶的石子相当于没变，于是留给后手的又是奇数台阶异或为0的状态
②当后手移动奇数台阶上的石子时，留给先手的奇数台阶异或非0，根据Nim游戏，先手总能
找出一种方案使奇数台阶异或为0

因此无论后手如何移动，先手总能通过 *** 作把奇数异或为0的情况留给后手，当奇数台阶全为0时，只留下偶数台阶上有石子。


（核心就是：先手总是把奇数台阶异或为0的状态留给对面，即总是将必败态交给对面）

因为偶数台阶上的石子要想移动到地面，必然需要经过偶数次移动，又因为奇数台阶全0的情况是留给后手的，
因此先手总是可以将石子移动到地面，当将最后一个（堆）石子移动到地面时，后手无法 *** 作，即后手失败。


*/
#include

using namespace std;

int main(){
    
    int res = 0;
    int n;
    cin >> n;
    
    for(int i = 1; i <= n; i++){
        
        int x;
        cin >> x;
        if(i % 2) res ^= x;
    }
    
    if(res) puts("Yes");
    else puts("No");
    
    return 0;
}

集合-Nim游戏

#include
#include
#include

using namespace std;

const int N = 110, M = 10010;
int n, m;
// sg值; 可选集合中的数
int f[M], s[N];

int sg(int x){
    
    if(f[x] != -1) return f[x];
    
    unordered_set<int> S;
    for(int i = 0; i < m; i++){
        
        int sum = s[i];
        // 求x能到达的状态的sg值
        if(x >= sum) S.insert(sg(x - sum));
    }
    
    // 求x(不在能到达的状态中)最小的自然数
    for(int i = 0; ;i++){
        
        if(!S.count(i)){
            
            return f[x] = i;
        }
    }
}

int main(){
    
    cin >> m;
    for(int i = 0; i < m; i++) cin >> s[i];
    cin >> n;
    
    memset(f, -1, sizeof(f));
    
    int res = 0;
    
    for(int i = 0; i < n; i++){
        
        int x;
        cin >> x;
        // 对初始状态的sg值进行异或
        res ^= sg(x);
    }
    
    if(res) puts("Yes");
    else puts("No");
    
    return 0;
}

拆分-Nim游戏

/*
SG函数定理：多个独立局面的SG的值,等于这些局面SG值的异或和
可以将a[i]拆分为(b[j], b[k]), 相当于一个局面被拆分成了两个局面
由SG定理得, sg(b[j], b[k]) = sg(b[j])^sg(b[k])
所以求得初始时每堆石子sg的异或值,如果非0则必胜,否则必败
*/
#include
#include
#include

using namespace std;

const int N = 110;

int n;
int f[N];

int sg(int x){
    
    if(f[x] != -1) return f[x];
    
    unordered_set<int> S;
    for(int i = 0; i < x; i++){
        for(int j = 0; j <= i; j++){  // 规定j不大于i, 避免重复
            
            S.insert(sg(i) ^ sg(j));  // sg定理
        }
    }
    
    // 求出当前局面能到达的局面SG值 之外的最小的自然数
    for(int i = 0; ; i++){
        
        if(!S.count(i)){
            
            return f[x] = i;
        }
    }
}

int main(){
    
    memset(f, -1, sizeof(f));
    
    cin >> n;
    int res = 0;
    
    while(n--){
        
        int x;
        cin >> x;
        res ^= sg(x);
    }
    
    if(res) puts("Yes");
    else puts("No");
    
    return 0;
}