数论

https://zhuanlan.zhihu.com/p/35060143

质数

定义：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数。

（1）质数的判定————试除法 O(sqrt(n))

for循环的判定推荐用 i <= n / i；不用 i * i <= n 或者 i <= sqrt(n)。
所以它的时间一定是sqrt(n)

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

（2）分解质因数————试除法 O(sqrt(n))

从小到大尝试所有因数，n中最多只包含一个大于sqrt(n)的质因子，可以像之前的那样判断到根号n，最后单独判断根号n是不是因子
时间不一定是sqrt(n)，时间复杂度在O(logn)-O(sqrt(n))之间。
把x分解为 $x = p_1^{k_1}p_2^{k_2}...p_j^{j_2}$ ， $p_j$ 都是质数。

void divide(int x){
    for(int i = 2; i <= x / i; i++){
        if (x % i == 0){  //一定是质数 
            int t = 0;
            while(x % i == 0){
                x /= i;
                t++;
            }
            cout << i << ' ' << t << endl;
        }
    }
    if(x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

（3）筛质数

朴素筛法、埃氏筛法和线性筛法，视频下面的评论也有总结
https://blog.csdn.net/Satur9/article/details/104229407
朴素筛法 O(n * logn)
把1~n中2的倍数，3的倍数， 4的倍数……都删除，那么剩下的数就都是质数了。
图片说明

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

埃氏筛法 O(nlog(logn))
我们会发现4的倍数也是2的倍数，所有我们只需要把所有质数的倍数删除就好。
图片说明

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

线性法 O(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;
        }
    }
}

定理： 1-n中有 $\frac{n}{logn}$ 个质数。
总结：
1．普通的筛素数的原理是一个素数的倍数必须不是素数。
2．改进的筛素数的原理是每个合数必有一个最小素因子，根据每个最小素因子去访问合数就能防止合数被重复访问。

约数

（1）试除法求一个数的所有约数

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

（2）约数个数

$N = p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$
约数个数 $n = (\alpha_1 + 1)(\alpha_2 + 1)...(\alpha_k + 1)$ 视频的第48分钟左右
这里题目是要求n个数的乘积的约数个数，如果先求乘积会爆int，所以直接求所有数的质因数和他们的个数1，再用公式。

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

（3）约数之和

$sum = (p_1^0 + p_1^1 + ... + p_1^{\alpha_1})(p_2^0 + p_2^1 + ... + p_2^{\alpha_2})...(p_k^0 + p_k^1 + ... + p_k^{\alpha_k})$
求primes和上一题一样，最后res的求法不一样。

    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;

（4）欧几里得算法

a 和 b 的公约数等于 b 和 a mod b 的公约数。任意整数与0的最大公约数是这个整数。
图片说明

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a; //b = 0时，a和b的公约数是a 
}

欧拉函数

图片说明

求每个数的欧拉函数

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

求1-n的欧拉函数之和（筛法）

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

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

快速幂

求 $a^k$ mod p 朴素做法 O(k)
图片说明
快速幂的核心思路是反复平方
把k拆成2的幂次之和

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

if(b & 1) 判断是不是奇数跟if(n%2==1)这个是一样的
n&1,将n变成二进制跟二进制的1 00000000 00000001按位做与操作。这时，只要n的最右边一位是1，结果就不是0，为true，

提问：LL res = 1 % p; 和写成 LL res = 1 是有什么区别吗？
答：p = 1, b = 0的时候，第一种结果是0，第二种结果是1。（也就是 1 % 1 = 0）
图片说明

快速幂求逆元

同余式是数论的基本概念之一，设m是给定的一个正整数，a、b是整数，若满足m|(a-b)，则称a与b对模m同余，记为a≡b(mod m)，或记为a≡b(m)。

称 x 为 b 的模 m 乘法逆元
性质：
图片说明

费马小定理： $a^{p-1} ≡ 1(mod p)$
图片说明

所以实质是求 $a^{p-2} mod p$ ，所以

if(a % p == 0) puts("impossible");
else cout << qmi(a, p - 2, p) << endl;

扩展欧几里得算法

https://blog.csdn.net/destiny1507/article/details/81750874

扩展欧几里得算法

这里扩展gcd，直接递归求出x，y。

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

图片说明

线性同余

图片说明
用exgcd得到 $ax + my' = d$ ，要求出 $ax + my' = b$ ，需要在第一个式子左右两边乘上 $\frac{b}{d}$ 。

        int a, b, m, x, y;
        cin >> a >> b >> m;
        int d = exgcd(a, m, x, y);
        if (b % d) puts("impossible");
        else printf("%d\n", (LL)b / d * x % m);

图片说明

中国剩余定理

比较复杂，有空可以看看，在week6习题课，或者可以直接看题目对应的视频如下
https://www.acwing.com/video/273/

#include <bits/stdc++.h>

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;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x; 
    return d;
}

int main(){
    int n;
    cin >> n;
    LL x = 0, m1, a1;
    cin >> m1 >> a1;
    for (int i = 0; i < n - 1; i ++ ){
        LL m2, a2;
        cin >> m2 >> a2;
        LL k1, k2;
        LL d = exgcd(m1, -m2, k1, k2);
        if ((a2 - a1) % d){
            x = -1;
            break;
        }
        k1 *= (a2 - a1) / d;
        k1 = (k1 % (m2/d) + m2/d) % (m2/d);

        x = k1 * m1 + a1;

        LL m = abs(m1 / d * m2);
        a1 = k1 * m1 + a1;
        m1 = m;
    }
    if (x != -1) x = (x % m1 + m1) % m1;

    cout << x << endl;
    return 0;
}

高斯消元

用于解方程组。在n³的时间内解含n个未知数的n个多元线性方程组。
结果：无解、无穷多组解、唯一解
https://blog.csdn.net/hellocsz/article/details/90488430
初等行列变换：

把某一行乘一个非零的数
交换某两行
把某行的若干倍加到另一行

#include <bits/stdc++.h>

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;
        for(int i = r; i < n; i++){
            if(fabs(a[i][c]) > fabs(a[t][c]) ) t = i;
        }

        if(fabs(a[t][c]) < eps) continue; //最大系数为0 

        //交换到上面
        for(int i = c; i < n + 1; i++ ) swap(a[t][i], a[r][i]);
        //把系数变为1 
        for(int i = n; i >= c; i--) a[r][i] /= a[r][c];
        //将下面所有行的第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[j][n] * a[i][j];

    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++) printf("%.2lf\n", a[i][n]);
    }else if(t == 1)  puts("Infinite group solutions");
    else puts("No solution");
    return 0;
}

应用更多的是高斯消元解异或线性方程组
https://www.acwing.com/activity/content/problem/content/954/

int gauss(){
    int c, r;
    for(c = 0, r = 0; c < n; c++){
        int t = r;
        for(int i = r; i < n; i++){
            if(a[i][c]) t = i;
        }

        if(a[t][c] == 0) continue; //最大系数为0 

        //交换到上面
        for(int i = c; i < n + 1; i++ ) swap(a[t][i], a[r][i]);
        //把系数变为1 (0，1方程组 这一步不需要了)
        //for(int i = n; i >= c; i--  a[r][i] /= a[r][c];
        //将下面所有行的第c列消为0 
        for(int i = r + 1; i < n; i++){
            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; //有唯一解 
}

组合计数

图片说明
有递推公式：

求 $C_a^b$ $mod(10^9+7)$

(1) 方法一：1 ≤ n ≤ 10000, 1 ≤ b ≤ a ≤ 2000

#include <bits/stdc++.h>

using namespace std;

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

int n;
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] + c[i - 1][j - 1]) % mod;
        }
    }
}

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

(2) 方法二： 1 ≤ n ≤ 10000, 1 ≤ b ≤ a ≤ $10^5$

用快速幂求逆元
图片说明

#include <bits/stdc++.h>

using namespace std;

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

int fact[N], infact[N];

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

int main(){
    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;
    }

    int n;
    cin >> n;
    while(n--){
        int a, b;
        cin >> a >> b;
        printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
    }
    return 0;
}

图片说明

(3) 方法三：1 ≤ n≤ 20, 1 ≤ b ≤ a ≤ $10^{18}$ , 1 ≤ p ≤ $10^5$

卢卡斯定理 https://baike.baidu.com/item/lucas/4326261?fr=aladdin
会用这个结论就行
图片说明

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int qmi(int a, int b, int p){
    int res = 1;
    while(b){
        if(b & 1) res = res * (LL)a % p;
        a = a * (LL) a % p;
        b >>= 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;
        printf("%d\n", lucas(a, b, p));
    }
    return 0;
}

(4) 1 ≤ b ≤ a ≤ 5000 不取模，需进行高精度运算

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 5010;

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

int main(){
    int a, b;
    cin >> a >> b;
    get_primes(a);
    for (int i = 0; i < cnt; i ++ ){
        int p = primes[i];
        sum[i] = get(a, p) - get(a - b, p) - get(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]);

    for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]);
    puts("");
    return 0;
}

(5) 满足条件的01序列

#include <bits/stdc++.h>

using namespace std;

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

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

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

    int a = n * 2, b = n;
    int res = 1;
    for (int i = a; i > a - b; i -- ) res = (LL)res * i % mod;

    for (int i = 1; i <= b; i ++ ) res = (LL)res * qmi(i, mod - 2, mod) % mod;

    res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;
    cout << res << endl;
    return 0;
}

容斥原理

图片说明
求能被整除的数暴力算法O(nm)

#include <bits/stdc++.h>

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;
    for(int i = 1; i < 1 << m; i++){
        int t = 1, s = 0;
        for(int j = 0; j < m; j++){
            if(i >> j & 1){
                if((LL)t * p[j] > n){
                    t = -1;
                    break;
                }
                t *= p[j];
                s++;
            }
        }
        if(t != -1){
            if(s % 2) res += n / t;
            else res -= n / t;
        }
    }
    cout << res << endl;
    return 0;
}

简单博弈论

Nim游戏
图片说明

#include <bits/stdc++.h>

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

台阶-Nim游戏
一个简单变种

#include <bits/stdc++.h>

using namespace std;

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

集合-Nim游戏

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 10010;

int n, m;
int s[N], f[M];


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];
        if (x >= sum) S.insert(sg(x - sum));
    }

    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;
        res ^= sg(x);
    }
    if (res) puts("Yes");
    else puts("No");
    return 0;
}

拆分-Nim游戏

#include <bits/stdc++.h>

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 ++ )
            S.insert(sg(i) ^ sg(j));

    for(int i = 0; ; i ++)
        if(!S.count(i))
            return f[x] = i;
}

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

模板-第四讲 数学知识

数论

质数

（1）质数的判定————试除法 O(sqrt(n))

（2）分解质因数————试除法 O(sqrt(n))

（3）筛质数

约数

（1）试除法求一个数的所有约数

（2）约数个数

（3）约数之和

（4）欧几里得算法

欧拉函数

求每个数的欧拉函数

求1-n的欧拉函数之和（筛法）

快速幂

快速幂求逆元

扩展欧几里得算法

扩展欧几里得算法

线性同余

中国剩余定理

高斯消元

组合计数

求

(1) 方法一：1 ≤ n ≤ 10000, 1 ≤ b ≤ a ≤ 2000

(2) 方法二： 1 ≤ n ≤ 10000, 1 ≤ b ≤ a ≤

(3) 方法三：1 ≤ n≤ 20, 1 ≤ b ≤ a ≤ , 1 ≤ p ≤

(4) 1 ≤ b ≤ a ≤ 5000 不取模，需进行高精度运算

(5) 满足条件的01序列

容斥原理

简单博弈论

模板-第四讲数学知识

求 $C_a^b$ $mod(10^9+7)$

(2) 方法二： 1 ≤ n ≤ 10000, 1 ≤ b ≤ a ≤ $10^5$

(3) 方法三：1 ≤ n≤ 20, 1 ≤ b ≤ a ≤ $10^{18}$ , 1 ≤ p ≤ $10^5$