其他

1.平衡三进制 :mark一下，放砝码问题，梦回计组pre

2.一个正整数n本身和他各位之和模9同余

数论

质数

定义

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

试除法判定质数

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

试除法分解质因数

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

朴素筛法求素数

求2~n所有素数

int primes[N], cnt;     // primes[]存储所有素数
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 + i; j <= n; j += i)
            st[j] = true;
    }
}

优化(小于x^2的x的倍数在扫描更小的数的时候已经被标记过了)

int primes[N], cnt;     // primes[]存储所有素数
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/i; j ++)
            st[i*j] = true;
    }
}

线性筛法求素数

保证每个数被它的最小质因子筛掉

int primes[N], cnt;     // primes[]存储所有素数
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 ++ )
        {
            st[primes[j] * i] = true; //primes[j]小于等于i的最小质因子
            if (i % primes[j] == 0) break; //保证primes[j]小于等于i的最小质因子
        }
    }
}

约数

定义

若整数n除以整数d的余数为0，即d能整除n，则称d是n的约数,n是d的倍数

试除法求所有约数

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

约数个数和约数之和

如果 N = p1^c1 * p2^c2 * ... *pk^ck //pi为从小到大互不相同的质数
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

欧几里得算法

快速求得 a 和 b 的最大公约数

int gcd(int a, int b) { // 欧几里得算法
    return b == 0 ? a : gcd(b, a % b);
}

最大公约数性质

a与b互质:gcd(a,b)==1

gcd(x, y)=gcd(x, y−x)
gcd(x, y)=gcd(y, x % y)
gcd(x, y) = gcd(x, -y)
gcd(x, 0) = x

有n个数，gcd() = gcd(，gcd()) (结合律，证明左边式子<=右边式子，右边式子<=左边式子)

最小公倍数

lcm(x,y) = x*y/gcd(x,y)

欧拉函数

互质： $若则互质$

对正整数m，欧拉函数是小于等于m的正整数中与m互质的数的数目.

利用容斥原理

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. $中与互质的数的和为$

2. $若互质，则$

筛法求欧拉函数(求2~N中每个数的欧拉函数)

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

费马小定理与欧拉定理

同余

定义

$若整数和整数除以正整数的余数相等，则称模同余，记为$

性质

1.若，且c与m互质，则（两边同除c，证明欧拉定理用到）(一般形式，若，，则)

2.若，且，则（加法）

3若，且，则（乘法）

快速幂

求 m^k mod p，时间复杂度 O(logk)。

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

卡特兰数

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

乘法逆元

如果只是保证b,m互质，乘法逆元可以通过求解同余方程得到

意义(为什么需要逆元？)

$(a + b) \% p = (a\%p + b\%p) \%p \quad (正确) \\ (a - b) \% p = (a\%p - b\%p) \%p \quad (正确) \\ (a * b) \% p = (a\%p * b\%p) \%p \quad (正确) \\ (a / b) \% p = (a\%p / b\%p) \%p\quad (错误) \\$

当很大需要取模时，如果a与b之间是除法运算，则无法像加减乘那样分开取模运算后再取模，所以需要乘法逆元

$(a / b) \% p = (a*b^{-1}) \%p = (a\%p * b^{-1}\%p) \%p\quad (正确)$

裴蜀定理

裴蜀定理，又称贝祖定理（Bézout’s lemma）。是一个关于最大公约数的定理。

其内容是：设a,b是不全为零的整数，则存在整数x,y , 使得ax+by = gcd(a,b) .

令对更一般的方程，它有解当且仅当，可以先求出的一组特解，再同时乘上，得到的特解，方程的通解集合可以表示为

$x=\frac{c}{d}x_0+k\frac{b}{d},y=\frac{c}{d}y_0-k\frac{a}{d}\quad(k \in \Z)$

裴蜀定理可以扩展到多个整数，设是个整数，，则存在整数使得$a_1x_1+a_2x_2+…+a_n*x_n=d$

扩展欧几里得算法

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

线性同余方程

特解

给定整数,求一个整数满足，或者无解。因为未知数的指数为1，所以称为一次同余方程，也称为线性同余方程。

$ax \equiv b \pmod{m} $等价于$ ax-b $是$ m $的倍数，设为$ -y $倍。于是方程可以改写为$ ax+my = b $，根据裴蜀定理可以知道方程有解当且仅当$ \gcd(a,m)|b $，采用扩展欧几里得算法得出$ ax_0+by_0=\gcd(a,m) $的一组解$ x_0,y_0 $，然后$ x = x_0 * b/\gcd(a,m)$，就是原线性同余方程的一组解

通解

方程的通解是所有模与同余的整数

证明:联立下面两式

$a*x_1+m*y_1 = b \\ a*x_2+m*y_2 = b$

得

$a*(x_1-x_2) = m*(y_2-y_1)$

令，上式两边同时除以得

$\frac{a}{d}*(x_1-x_2) = \frac{m}{d}*(y_2-y_1)$

因为为和的最大公约数，所以和互质，且$\frac{m}{d}|\frac{a}{d}(x_1-x_2) $，所以$ \frac{m}{d}|(x_1-x_2) $，得到$ x_1-x_2 = km/d $，即$ x_2 = x_1 + k*m/d$

中国剩余定理(CRT)

设是两两互质的整数，，,是线性同余方程的一个解，对于任意的个整数，方程组

$\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_n \pmod{m_n} \end{cases}$

有整数解，解为

扩展CRT

如果不两两互质，那么可以使用扩展欧几里得算法将两个式子合并成一个式子，合并n次即可得到最后答案，如

$(a)\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \end{cases}$

等价于

$\begin{cases} x = k_1*m_1 + a_1(3) \\ x = k_2*m_2 + a_2 \\ \end{cases}$

联立可得

$k_1*m_1 - k_2*m_2 = a_2 - a_1$

有解当且仅当，用扩展欧几里得算法可以求出特解，通解为

$\begin{cases} k_1=k'_1 + k*\frac{m_2}{d} (1)\\ k_2=k'_2 + k'*\frac{m_1}{d}(2) \quad k,k' \in \Z \quad d=gcd(m_1, m_2) \end{cases}$

不妨将(1)式代入(3)式，可以得到的通解

$x=k'_1*m_1+a_1+k*\frac{m_1*m_2}{d}$

即两个方程可以合并为一个

$(b) \quad x \equiv k'_1*m_1+a_1 \pmod{\frac{m_1*m_2}{d}}$

其中

为什么两个方程能合并成一个呢？只需要证明上面方程组(a)的解集与(b)相等即可，可以先设是(b)的一个解，推出也是(a)的一个解，再设是(a)的一个解，推出也是(b)的一个解，显然易证

例题

给定个整数和，求一个最小非负整数，满足，不存在输出

#include <iostream>

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

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

        k1 = (k1 % (a2 / d) + a2 / d) % (a2 / d);

        x = k1 * a1 + m1;

        a1 = a1 / d * a2;

        m1 = x;
    }


    x = (m1 % a1 + a1) % a1;

    cout << x << endl;
    return 0;

}

博弈论

NIM游戏

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

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

必胜态:可以到某一个必败态

必败态:无论如何选取都只能到必胜态

定理： NIM博弈先手必胜，当且仅当 A1 ^ A2 ^ … ^ An != 0

公平组合游戏ICG

若一个游戏满足：

1.由两名玩家交替行动；

2.在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
3.不能行动的玩家判负；
则称该游戏为一个公平组合游戏。
NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即：mex(S) = min{x}, x属于自然数，且x不属于S

SG函数

在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1, y2, …, yk，定义SG(x)为x的后继节点y1, y2, …, yk 的SG函数值构成的集合再执行mex(S)运算的结果，即：SG(x) = mex({SG(y1), SG(y2), …, SG(yk)})
特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G) = SG(s)。

有向图游戏的和

设G1, G2, …, Gm 是m个有向图游戏。定义有向图游戏G，它的行动规则是任选某个有向图游戏Gi，并在Gi上行动一步。G被称为有向图游戏G1, G2, …, Gm的和。
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和，即：SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm)

定理

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

算法数学基础知识

其他

数论

质数

定义