数学（待更新...)

数学知识

• • 写在前面的话：
  • 质数
  • • • • 例题：试除法判断质数
        • 例题：分解质因数
        • 例题：筛质数
        • • 埃氏筛法
          • `调和级数`
          • 一个质数定理
          • 线性筛法
  • 约数
  • • • • • 一些公式：
        • 例题：试除法求约数
        • 例题：约数个数
        • 例题：约数之和
        • 例题：最大公约数
  • 欧拉函数
  • • • • 例题：欧拉函数
        • 例题：筛法求欧拉函数
      • 欧拉定理
      • • 费马小定理
  • 快速幂
  • • • • 例题：快速幂求逆元
        • • 乘法逆元定义
  • 扩展欧几里得算法
  • • • • • 裴蜀定理
        • 例题：线性同余方程
  • 中国剩余定理
  • • • • 例题：表达整数的奇怪方式
        • 例题：表达整数的奇怪方式
  • 高斯消元
  • 容斥原理
  • • • • 例题：能被整除的数
  • 求组合数
  • 博弈论
  • • • • 例题： N I M NIM NIM游戏
        • • Mex运算
        • S G SG SG函数
        • • 有向图游戏的和
        • 例题：集合- N I M NIM NIM游戏

写在前面的话：

1. 牢记是否会出现溢出问题！必要时用 l o n g   l o n g long long long long

质数 例题：试除法判断质数

#include 

using namespace std;

bool is_prime(int n)
{
    if (n < 2) return false; //质数的定义是从2开始
    for (int i = 2; i <= n / i; i++)
        if (n % i == 0) 
            return false;
    return true;
}
int main()
{
    int n; cin >> n;
    while (n--)
    {
        int a;
        cin >> a;
        if (is_prime(a)) puts("Yes");
        else puts("No");
    }
    return 0;
}

复杂度：真的 O ( n ) O(sqrt n) O(n ​)

例题：分解质因数

#include 

using namespace std;

void divide(int n)
{
    for (int i = 2; i <= n / i; i++)//一定最多有1个大于sqrt(n)的质因子
    {
        if (n % i == 0)//i一定是质数
        {
            int s = 0;
            while (n % i == 0)//只要能被i整除
            {
                n /= i;
                s ++;
            }
            cout << i << ' ' << s << endl;
        }
    }
    if (n > 1) cout << n << ' ' << 1 << endl;//如果分解完n>1那么这个数一定是n的质因子
}
int main()
{
    int n; cin >> n;
    while (n--)
    {
        int a; 
        cin >> a;
        divide(a);
        puts("");
    }
    return 0;
}

复杂度：最坏 O ( n ) O(sqrt n) O(n ​),最好情况 O ( log ⁡   n ) O(log n) O(log n)

例题：筛质数

普通筛法 复杂度 O ( n log ⁡ n ) O(nlog n) O(nlogn)

#include 
using namespace std;

const int N = 1e6 + 10;
int primes[N];
bool st[N];
//普通筛法
int get_primes(int n)
{
    int cnt = 0;
    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;
    }//注意枚举的是从下一个i的倍数开始，依次枚举i的倍数
    return cnt;
}
int main()
{
    int n; cin >> n;
    cout << get_primes(n) << endl;
    return 0;
}

埃氏筛法 调和级数

lim ⁡ n → ∞ 1 + 1 2 + ⋯ + 1 n   = ln ⁡   n   + C limlimits_{n→infty} 1+frac{1}{2} +dots +frac{1}{n}space = lnspace nspace + C n→∞lim​1+21​+⋯+n1​ =ln n +C

一个质数定理

1~n中有 n ln ⁡   n frac{n} {ln n} ln nn​ 个质数

复杂度 O ( n log ⁡ log ⁡ n ) O(nlog log n) O(nloglogn)

#include 
using namespace std;

const int N = 1e6 + 10;
int primes[N];
bool st[N];
//埃氏筛法
int get_primes(int n)
{
    int cnt = 0;
    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;
        }
            
    }
    return cnt;
}
int main()
{
    int n; cin >> n;
    cout << get_primes(n) << endl;
    return 0;
}

线性筛法

复杂度 O ( n ) O(n) O(n)

#include 
using namespace std;

const int N = 1e7 + 10;
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;
        }
    }
}
int main()
{
    int n; cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

不懂为什么 N N N开到 1 e 7 1e7 1e7才能过！！！！

别人的代码只需要到 1 e 6 1e6 1e6QAQ

天呐！我找到问题了！！！！

j→primes[j]

约数 一些公式：

若 ： N = p 1 c 1 × p 2 c 2 × ⋯ × p k c k N={p_1}^{c_1}times {p_2}^{c_2} times dots times {p_k}^{c_k} N=p1​c1​×p2​c2​×⋯×pk​ck​

约数个数： ( c 1 + 1 ) ( c 2 + 1 ) … ( c k + 1 ) (c_1+1)(c_2+1) dots (c_k+1) (c1​+1)(c2​+1)…(ck​+1)

约数之和： ( p 1 0 + p 1 1 + ⋯ + p 1 c 1 ) × ⋯ × ( p k 0 + p k 1 + ⋯ + p k c k ) (p_1^0+p_1^1+dots +p_1^{c_1})times dots times (p_k^0 +p_k^1+dots +p_k^{ck}) (p10​+p11​+⋯+p1c1​​)×⋯×(pk0​+pk1​+⋯+pkck​)

欧几里得算法(辗转相除法):

复杂度 O ( log ⁡ n ) O(log n) O(logn)

常识(?)：

|代表整除符号

i f (   d ∣ a , d ∣ b ) → d ∣ ( a + b ) & & d ∣ ( a x + b y ) if( d|a ,d|b) → d|(a+b) && d|(ax+by) if( d∣a,d∣b)→d∣(a+b)&&d∣(ax+by)

( a , b ) = ( b , a % b ) (a,b)=(b,a%b) (a,b)=(b,a%b)

a % b = a − ⌊ a b ⌋ × b a%b=a - ⌊frac{a}{b}⌋times b a%b=a−⌊ba​⌋×b

​ ↓

( a , b ) = ( b , a − c × b ) (a,b)=(b,a-ctimes b) (a,b)=(b,a−c×b)

例题：试除法求约数

T i p ： Tip： Tip： i n t int int范围内最多的约数个数大约为 1500 1500 1500

复杂度 O ( n ) O(sqrt n) O(n ​)

#include 
#include 
#include 
using namespace std;

vector get_divisors(int n)
{
    vectorres;
    for (int i = 1; i <= n / i; i++)
    {
        if (n % i == 0)
        {
            res.push_back(i);
            if (n / i != i) res.push_back(n / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}
int main()
{
    int n; cin >> n;
    while(n--)
    {
        int a; cin >> a;
        auto res = get_divisors(a);
        for (auto t : res)
            cout << t << ' ';
        cout << endl;
    }
    return 0;
}

注意:只有这里的 i i i从 1 1 1开始枚举

例题：约数个数

（需要先分解质因数，参考上面代码）

#include 
#include 

using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
    int n; cin >> n;
    unordered_mapprimes;
    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 prime : primes) res = res * (prime.second + 1) % mod;
    cout << res << endl;
    return 0;
}

例题：约数之和

#include 
#include 

using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
    int n; cin >> n;
    unordered_mapprimes;
    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 prime : primes) 
    {
        int p = prime.first, a = prime.second;
        LL t = 1;
        while (a--) t = (t * p + 1) % mod;
        res = res * t % mod;//有多少个质因子就乘多少次
    }
    cout << res << endl;
    return 0;
}

对于t的解释：

初始：t=p+1

迭代 2 2 2次：t=p(p+1)+1=p^2+p+1

迭代 3 3 3次：t=p^3+p^2+p+1

… dots …

迭代 a a a次：t=p^a+...+p^1+1

要循环指数次~

（此处的 1 = p 0 1=p^0 1=p0）

太妙了！

例题：最大公约数

#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 ) : φ(n): φ(n): 1~n中与n互质的数的个数

eg: φ ( 6 ) = 2    { 1 , 5 } φ(6)=2 {1,5} φ(6)=2  {1,5}

若 N = p 1 a 1 p 2 a 2 … p k a k , ( p n 为 N 的 质 因 子 ) N=p_1^{a_1}p_2^{a_2}dots p_k^{a_k},(p_n为N的质因子) N=p1a1​​p2a2​​…pkak​​,(pn​为N的质因子)

φ ( N ) = N ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) … ( 1 − 1 p k ) φ(N)=N(1-frac{1}{p_1})(1-frac{1}{p_2})dots (1-frac{1}{p_k}) φ(N)=N(1−p1​1​)(1−p2​1​)…(1−pk​1​)

证明：由容斥原理

例题：欧拉函数

复杂度 O ( n n ) O(nsqrt n) O(nn ​)

#include 
using namespace std;

const int N = 110;

int main()
{
    int n; cin >> n;
    while (n--)
    {
        int a; cin >> a;
        int res = a;
        for (int i = 2; i <= a / i; i++)//i从2开始，与其他做好区分
        {
            if (a % i == 0)
            {
                res = res / i * (i - 1);//先除后乘防止爆int
                while (a % i == 0) a /= i;
            }
        }
        if (a > 1) res = res / a * (a - 1);
        cout << res << endl;
    }
    return 0;
}

例题：筛法求欧拉函数

一些证明：

当i%primes[j]==0

φ ( i ) = i ( 1 − 1 p 1 ) … ( 1 − 1 p k ) φ(i)=i(1-frac{1}{p_1})dots (1-frac{1}{p_k}) φ(i)=i(1−p1​1​)…(1−pk​1​)

φ ( p r i m e s [ j ] × i ) = p r i m e s [ j ] × i ( 1 − 1 p 1 ) … ( 1 − 1 p k ) = p r i m e s [ j ] × φ ( i ) φ(primes[j]times i)=primes[j]times i(1-frac{1}{p_1})dots (1-frac{1}{p_k}) \ =primes[j]times φ(i) φ(primes[j]×i)=primes[j]×i(1−p1​1​)…(1−pk​1​)=primes[j]×φ(i)

当i%primes[j]!=0

φ ( i ) = i ( 1 − 1 p 1 ) … ( 1 − 1 p k ) φ(i)=i(1-frac{1}{p_1})dots (1-frac{1}{p_k}) φ(i)=i(1−p1​1​)…(1−pk​1​)

φ ( p r i m e s [ j ] × i ) = p r i m e s [ j ] × i ( 1 − 1 p 1 ) … ( 1 − 1 p k ) ( 1 − 1 p r i m e s [ j ] ) φ(primes[j]times i)=primes[j]times i(1-frac{1}{p_1})dots (1-frac{1}{p_k})(1-frac {1}{primes[j]}) φ(primes[j]×i)=primes[j]×i(1−p1​1​)…(1−pk​1​)(1−primes[j]1​)

​ = p r i m e s [ j ] × φ ( i ) ( 1 − 1 p r i m e s [ j ] ) =primes[j]times φ(i)(1-frac {1}{primes[j]}) =primes[j]×φ(i)(1−primes[j]1​)

​ = ( p r i m e s [ j ] − 1 ) × φ ( i ) =(primes[j]-1)times φ(i) =(primes[j]−1)×φ(i)

此时 ( p r i m e s [ j ] 是 新 的 质 因 子 就 要 再 乘 上 它 ) (primes[j]是新的质因子就要再乘上它) (primes[j]是新的质因子就要再乘上它)

φ ( i ) φ(i) φ(i)是递推来的，无需公式计算~

#include 
using namespace std;

const int N = 1e6 + 10;
int phi[N],primes[N],cnt;
bool st[N];

typedef long long LL;

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

}

int main()
{
    int n; cin >> n;
    LL res = 0;
    get_eulers(n);
    for (int i = 1; i <= n; i++) res += phi[i];
    cout << res << endl;
    return 0;
}

欧拉定理

若m与n互质，则 m φ ( n ) ≡ 1 ( m o d    n ) m^{φ(n)}≡1(mod n) mφ(n)≡1(modn)

证明：

1~n中， a 1 , a 2 , … , a φ ( n ) a_1,a_2,dots ,a_{φ(n)} a1​,a2​,…,aφ(n)​互质，因为m与n互质，所以 m a 1 , m a 2 , … , m a φ ( n ) ma_1,ma_2,dots ,ma_{φ(n)} ma1​,ma2​,…,maφ(n)​互质 ( φ ( n ) φ(n) φ(n)个 m m m)

so m φ ( n ) ( a 1 a 2 … a φ ( n ) ) ≡ ( a 1 a 2 … a φ ( n ) ) ( m o d    n ) → m φ ( n ) ≡ 1 ( m o d    n ) m^{φ(n)}(a_1a_2dots a_{φ(n)})≡(a_1a_2dots a_{φ(n)})(mod n)→m^{φ(n)}≡1(mod n) mφ(n)(a1​a2​…aφ(n)​)≡(a1​a2​…aφ(n)​)(modn)→mφ(n)≡1(modn)

欧拉定理的一个特例：

费马小定理

当n为质数，我们称它为p,我们知道φ(p)=p-1

so m p − 1 ≡ 1 ( m o d    p ) m^{p-1}≡1(mod p) mp−1≡1(modp)

快速幂

原理：将次数化为二进制表示，某一位是 1 1 1就乘上这一位的底数的对应位数的次幂

复杂度 O ( log ⁡ k ) O(log k) O(logk) ( k k k为指数)

#include 
using namespace std;

int a, p, k;
typedef long long LL;//数论很多题目都要注意LL
int binpow(int a, int k, int p)
{
    int res = 1;
    while (k)//如果指数还没被分完
    {
        if (k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;//这里也要取模
    }
    return res;
}
int main()
{
    int n; cin >> n;
    while (n--)
    {
        cin >> a >> k >> p;
        cout << binpow(a, k, p) << endl;
    }
    return 0;
}

例题：快速幂求逆元 乘法逆元定义

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

也就是说：

a / b ≡ a × b − 1 ( m o d    m ) → 1 ≡ b − 1 × b ( m o d    m ) → 1 ( m o d    m ) ≡ b − 1 × b → b − 1 × b ( m o d    m ) ≡ b m − 1 a/b≡a×b^{-1}(mod m)→1≡b^{-1}times b(mod m)→1(mod m)≡b^{-1}times b→b^{-1}times b(mod m)≡ b^{m-1} a/b≡a×b−1(modm)→1≡b−1×b(modm)→1(modm)≡b−1×b→b−1×b(modm)≡bm−1

so

b − 1 ≡ b m − 2 ( m o d    m ) b^{-1}≡b^{m-2}(mod m) b−1≡bm−2(modm)

当然上述公式当且仅当 b , m b,m b,m互质时成立（即不成倍数关系），如果 b b b为 m m m的倍数，（为什么只限制不是倍数，因为 m m m为质数，如果不是倍数，那么 b , m b,m b,m一定互质！）那么 b % m = = 0 ! = 1 b%m==0!=1 b%m==0!=1（参照上面证明过程的公式）。

#include 
using namespace std;

int a, p;
typedef long long LL;
int binpow(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}
int main()
{
    int n; cin >> n;
    while (n--)
    {
        cin >> a >> p;
        if (a % p) cout << binpow(a, p - 2, p) << endl;
        else puts("impossible");
    }
    return 0;
}

扩展欧几里得算法

background:

裴蜀定理

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

--------

用于求解方程 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b) 的解

当 b = 0 b=0 b=0 时 a x + b y = a ax+by=a ax+by=a 故而 x = 1 , y = 0 x=1,y=0 x=1,y=0
当 b ≠ 0 b≠0 b​=0时

因为

g c d ( a , b ) = g c d ( b , a % b ) gcd(a,b)=gcd(b,a%b) gcd(a,b)=gcd(b,a%b)

g c d ( a , b ) = g c d ( b , a % b ) gcd(a,b)=gcd(b,a%b) gcd(a,b)=gcd(b,a%b)

而

b x ′ + ( a % b ) y ′ = g c d ( b , a % b ) bx'+(a%b)y'=gcd(b,a%b) bx′+(a%b)y′=gcd(b,a%b)

b x ′ + ( a % b ) y ′ = g c d ( b , a % b ) bx'+(a%b)y'=gcd(b,a%b) bx′+(a%b)y′=gcd(b,a%b)

b x ′ + ( a − ⌊ a b ⌋ × b ) y ′ = g c d ( b , a % b ) bx'+(a−⌊frac{a}{b}⌋times b)y'=gcd(b,a%b) bx′+(a−⌊ba​⌋×b)y′=gcd(b,a%b)

b x ′ + ( a − ⌊ a b ⌋ × b ) y ′ = g c d ( b , a % b ) bx'+(a−⌊frac{a}{b}⌋times b)y'=gcd(b,a%b) bx′+(a−⌊ba​⌋×b)y′=gcd(b,a%b)

a y ′ + b ( x ′ − ⌊ a b ⌋ × y ′ ) = g c d ( b , a % b ) = g c d ( a , b ) ay'+b(x′−⌊frac{a}{b}⌋times y')=gcd(b,a%b)=gcd(a,b) ay′+b(x′−⌊ba​⌋×y′)=gcd(b,a%b)=gcd(a,b)

a y ′ + b ( x ′ − ⌊ a b × y ′ ) = g c d ( b , a % b ) = g c d ( a , b ) ay'+b(x′−⌊frac{a}{b}times y')=gcd(b,a%b)=gcd(a,b) ay′+b(x′−⌊ba​×y′)=gcd(b,a%b)=gcd(a,b)

故而

x = y ′ , y = x ′ − ⌊ a b ⌋ × y ′ x=y',y=x'−⌊frac{a}{b}⌋times y' x=y′,y=x′−⌊ba​⌋×y′

#include 
using namespace std;

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

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

应用：

例题：线性同余方程

a × x ≡ b ( m o d    m ) ⇒ a × x + m × y = b a×x≡b(mod m)Rightarrow atimes x+mtimes y=b a×x≡b(modm)⇒a×x+m×y=b

上述等式有解当且仅当 g c d ( a , m ) ∣ b gcd(a,m)|b gcd(a,m)∣b,因此先用扩展欧几里得算法求出一组整数解 x 0 , y 0 x_0,y_0 x0​,y0​，使得 a × x 0 + m × y 0 = g c d ( a , m ) atimes x_0+mtimes y_0=gcd(a,m) a×x0​+m×y0​=gcd(a,m),然后再求要求的树是这一组数的几倍，即答案为 x = x 0 b g c d ( a , m ) % m x=x_0 frac{b}{gcd(a,m)}%m x=x0​gcd(a,m)b​%m，最后防止结果过大要对其取模。

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

int main()
{
    int n; cin >> n;
    while (n--)
    {
        int a, b, m, x, y;
        cin >> a >> b >> m;
        int d = exgcd(a, m, x, y);
        if (b % d) puts("impossible");
        else 
        {
            x = (LL)x * (b / d) % m;
            cout << x << endl;
        }
    }
    return 0;
}

中国剩余定理 例题：表达整数的奇怪方式

\证明
过程好复杂！！！不想打QAQ

打了 g e t get get到好多新玩法

$$
left{

begin{array}{ll}

x≡m_1(mod a_1)①

x≡m_2(mod a_2)②

dots

x≡m_n(mod a_n)

end{array}
right.
$$
end{document}

(为什么这里格式不对了！！！？）

先计算前两个线性同余方程组的解如下：

x = k 1 × a 1 + m 1 ③ x = k 2 × a 2 + m 2 ④ x=k_1times a_1+m_1③\x=k_2times a_2+m_2④ x=k1​×a1​+m1​③x=k2​×a2​+m2​④

③ = ④ ↓ k 1 × a 1 + m 1 = k 2 × a 2 + m 2 ↓ k 1 × a 1 − k 2 × a 2 = m 2 − m 1 ↓ 裴 蜀 定 理 k 1 a 1 − k 2 a 2 = g c d ( a 1 , − a 2 ) = k ( m 2 − m 1 ) 即 g c d ( 1 , − a 2 ) ∣ ( m 2 − m 1 ) ③= ④\downarrow\k_1times a_1+m_1=k_2times a_2+m_2\downarrow\k_1times a_1-k_2times a_2=m_2-m_1\downarrow裴蜀定理\k_1a_1-k_2a_2=gcd(a_1,-a_2)=k(m_2-m_1)即gcd(_1,-a_2)|(m_2-m_1) ③=④↓k1​×a1​+m1​=k2​×a2​+m2​↓k1​×a1​−k2​×a2​=m2​−m1​↓裴蜀定理k1​a1​−k2​a2​=gcd(a1​,−a2​)=k(m2​−m1​)即gcd(1​,−a2​)∣(m2​−m1​)

结论： k 1 , k 2 的 通 解 → 非 齐 次 = 齐 次 通 解 + 非 齐 次 通 解 k_1,k_2的通解rightarrow非齐次=齐次通解+非齐次通解 k1​,k2​的通解→非齐次=齐次通解+非齐次通解
g c d ( a 1 , − a 2 ) = d k 1 = k 1 + k a 2 d k 2 = k 2 + a 1 d ⇓ x = k 1 a 1 + m 1 ⏟ 更新后的m1 + a 2 d a 1 ⏟ 更新后的a1 k gcd(a_1,-a_2)=d\k_1=k_1+kfrac{a_2}{d}\k_2=k_2+frac{a_1}{d}\Downarrow x=underbrace{k_1a_1+m_1}_{text{更新后的m1}}+underbrace{frac{a_2}{d}a_1}_{text{更新后的a1}}k gcd(a1​,−a2​)=dk1​=k1​+kda2​​k2​=k2​+da1​​⇓x=更新后的m1 k1​a1​+m1​​​+更新后的a1 da2​​a1​​​k

例题：表达整数的奇怪方式

#include 
#include 
using namespace std;
typedef long long LL;

int 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;
    bool has_answer = true;
    LL a1, m1;
    cin >> a1 >> m1;
    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)
        {
            has_answer = false;
            break;
        }
        k1 *= (m2 - m1) / d;
        LL t = a2 / d;
        k1 = (k1 % t + t) % t;
        m1 = a1 * k1 + m1;
        a1 = abs(a1 / d * a2);
    }
    if (has_answer) 
        cout << (m1 % a1 + a1) % a1 << endl;
    else puts("-1");
    return 0;
}

高斯消元 容斥原理

求 n n n个圆组成的图形的面积：

S 1 + S 2 + ⋯ + S n − S 1 ∩ S 2 − S 1 ∩ S 3 − ⋯ − S 1 ∩ S n − S 2 ∩ S 3 − ⋯ − S n − 1 ∩ S n + S 1 ∩ S 2 ∩ S 3 + S 2 ∩ S 3 ∩ S 4 + ⋯ + S n − 2 ∩ S n − 1 ∩ S n … + ( − 1 ) n − 1 S 1 ∩ S 2 ∩ S 3 ∩ ⋯ ∩ S n S_1+S_2+dots +S_n\-S_1∩S_2-S_1∩S_3-dots -S_1∩S_n-S_2∩S_3-dots-S_{n-1}∩S_n\+S_1∩S_2∩S_3+S_2∩S_3∩S_4+dots+S_{n-2}∩S_{n-1}∩S_n\dots\+(-1)^{n-1}S_1∩S_2∩S_3∩dots ∩S_n S1​+S2​+⋯+Sn​−S1​∩S2​−S1​∩S3​−⋯−S1​∩Sn​−S2​∩S3​−⋯−Sn−1​∩Sn​+S1​∩S2​∩S3​+S2​∩S3​∩S4​+⋯+Sn−2​∩Sn−1​∩Sn​…+(−1)n−1S1​∩S2​∩S3​∩⋯∩Sn​

PS:

( n k ) 表 示 n 元 素 中 取 k 个 元 素 的 组 合 数 binom{n}{k}表示n元素中取k个元素的组合数 (kn​)表示n元素中取k个元素的组合数

公式:

∑ i = 0 n ( n k ) = 2 n ↓ C n 0 + C n 1 + ⋯ + C n n = 2 n displaystylesum_{i=0}^nbinom{n}{k}=2^n\downarrow \C_n^0+C_n^1+dots+C_n^n=2^n i=0∑n​(kn​)=2n↓Cn0​+Cn1​+⋯+Cnn​=2n

语言解释大概就是： n n n个物品里面选任意个的方案数 = = =从第 1 1 1个物品到第 n n n个物品抉择选或不选

上述定理的证明可用公式：

∑ i = 1 n ( − 1 ) i ( n k ) = 1 displaystylesum_{i=1}^{n}(-1)^{i}binom{n}{k}=1 i=1∑n​(−1)i(kn​)=1

拓展公式：

∑ i = 1 n ( − 1 ) i ( n i ) = 1 ↓ − ∑ i = 1 n ( − 1 ) i ( n i ) + C n 0 = − 1 + 1 = 0 ↓ ∑ i = 0 n ( − 1 ) i ( n i ) = 0 displaystylesum_{i=1}^{n}(-1)^{i}binom{n}{i}=1\downarrow\-displaystylesum_{i=1}^{n}(-1)^{i}binom{n}{i}+C_n^0=-1+1=0\downarrow\displaystylesum_{i=0}^{n}(-1)^{i}binom{n}{i}=0 i=1∑n​(−1)i(in​)=1↓−i=1∑n​(−1)i(in​)+Cn0​=−1+1=0↓i=0∑n​(−1)i(in​)=0

( 组 合 恒 等 式 ) (组合恒等式) (组合恒等式)

例题：能被整除的数

#include 
using namespace std;

const int N = 20;
int p[N];
typedef long long LL;

int main()
{
    int n, m;
    int res = 0;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
        cin >> p[i];
    for (int i = 1; i < 1 << m; i++)
    {
        int t = 1, cnt = 0;//质数集合的乘积
        for (int j = 0; j < m; j++)
        {
            if (i >> j & 1)
            {
                cnt++;//如果这一位是1，就记录，以便之后判断+-
                if ((LL)t * p[j] > n)
                {
                    t = -1;
                    break;
                }
                t *= p[j];
            }
        }
        if (t != -1)
        {
            if (cnt & 1) res += n / t;
            else res -= n / t;
        }
    }
    cout << res << endl;
    return 0;
}

求组合数 博弈论

公平组合游戏

若一个游戏满足：

1. 有两名玩家交替行动
2. 在游戏进行的任意时刻可以执行的合法行动与轮到哪位玩家无关
3. 不能行动的玩家判负

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

尼姆游戏（ N I M NIM NIM）属于公平组合游戏，但常见的棋类游戏，比如围棋就不是公平组合游戏，因为围棋交战双方分别只能落黑子和白子，胜负判定也比较负责，不满足条件 2 2 2和 3 3 3。

必胜状态：先手进行某一个操作，留给后手是一个必败状态时，对先手是一个必胜状态，即先手可以走到一个必败状态。

必败状态：先手无论如何操作，留个后手都是一个必胜状态时，对于先手来说是一个必败状态，即先手走不到任何一个必败状态。

结论：

假设 n n n堆石子，石子数目分别是 a 1 , a 2 , … , a n a_1,a_2,dots,a_n a1​,a2​,…,an​，如果 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n ≠ 0 a_1oplus a_2oplusdotsoplus a_nneq0 a1​⊕a2​⊕⋯⊕an​​=0，先手必胜，否则先手必败。

证明：

• 操作到醉后时每堆石子数都是 0 0 0, 0 ⊕ 0 ⊕ ⋯ ⊕ 0 = 0 0oplus 0oplusdots oplus 0=0 0⊕0⊕⋯⊕0=0
• 在操作过程中，如果 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = x ≠ 0 a_1oplus a_2oplusdotsoplus a_n=xneq0 a1​⊕a2​⊕⋯⊕an​=x​=0，那么玩家必然可以通过拿走某一堆的若干个石子将异或结果变为0。证明：设 x x x的二进制表示中最高位的 1 1 1在第 k k k位，那么在 a 1 , a 2 , … , a n a_1,a_2,dots ,a_n a1​,a2​,…,an​中，必然有一个数 a i a_i ai​的第 k k k位为 1 1 1，且 a i ⊕ x < a i a_ioplus x < a_i ai​⊕xai​⊕x}⊕⋯⊕an​=x⊕x=0
• 在操作过程中，如果 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = 0 a_1oplus a_2oplusdotsoplus a_n=0 a1​⊕a2​⊕⋯⊕an​=0，那么无论玩家怎么拿，必然会导致最终异或结果不为 0 0 0。反证法：假设玩家从第 i i i堆拿走若干个，这堆剩余数量为 a i ′ a_i' ai′​异或结果仍然是 0 0 0，那么 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a i ′ ⊕ ⋯ ⊕ a n = 0 a_1oplus a_2oplusdotsoplus a_i'oplusdotsoplus a_n=0 a1​⊕a2​⊕⋯⊕ai′​⊕⋯⊕an​=0，与上面得到的 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = 0 a_1oplus a_2oplusdotsoplus a_n=0 a1​⊕a2​⊕⋯⊕an​=0异或，结果为 0 0 0，得到 a i ⊕ a i ′ = 0 a_ioplus a_i'=0 ai​⊕ai′​=0，因为我们一定是拿走一部分的，所以 a i ≠ a i ′ a_ineq a_i' ai​​=ai′​，与假设矛盾，得证。

结论：

如果先手面对的局面是 a 1 ⊕ a 2 ⊕ … ⊕ a n ≠ 0 a_1⊕a_2⊕…⊕a_n≠0 a1​⊕a2​⊕…⊕an​​=0，那么先手总可以通过拿走某一堆若干个石子，将局面变成 a 1 ⊕ a 2 ⊕ … ⊕ a n = 0 a_1⊕a_2⊕…⊕a_n=0 a1​⊕a2​⊕…⊕an​=0，而后手一定会将局面变为 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n ≠ 0 a_1oplus a_2oplusdotsoplus a_nneq0 a1​⊕a2​⊕⋯⊕an​​=0。如此重复，最后一定是后手面临最终没有石子可拿的状态，先手必胜，反之先手必败。

例题： N I M NIM NIM游戏

Tip:   0 ⊕ x = x 0oplus x=x  0⊕x=x

#include 
using namespace std;

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

Mex运算

设 S S S表示一个非负整数集合，定义 m a x ( S ) max(S) max(S)为求出不属于集合 S S S的最小的非负整数的运算。

S G SG SG函数

在有向图游戏中，对于每个节点 x x x，设从 x x x出发有 k k k条有向边，分别到达节点 y 1 , y 2 , … , y k y_1,y_2,dots,y_k y1​,y2​,…,yk​，定义 S G ( x ) SG(x) SG(x)为 x x x的后继节点 y 1 , y 2 , … , y k y_1,y_2,dots,y_k y1​,y2​,…,yk​的 S G SG SG函数值构成的集合再执行 m e x mex mex运算的结果，即：

S G ( x ) = m e x ( { S G ( y 1 ) , S G ( y 2 ) ) , …   . S G ( y k ) } ) SG(x)=mex({SG(y_1),SG(y_2)),dots.SG(y_k)}) SG(x)=mex({SG(y1​),SG(y2​)),….SG(yk​)})

整个有向图游戏 G G G的 S G SG SG函数值被定义为有向图游戏起点 s s s的 S G SG SG函数值，即 S G ( G ) = S G ( s ) SG(G)=SG(s) SG(G)=SG(s)。

有向图游戏的和

设 G 1 , G 2 , … , G m G_1,G_2,dots,G_m G1​,G2​,…,Gm​是 m m m个有向图游戏。定义有向图游戏 G G G，它的行动规则是任选某个有向图游戏 G i G_i Gi​上行动一步， G G G被称为有向图游戏 G 1 , G 2 , … , G m G_1,G_2,dots,G_m G1​,G2​,…,Gm​的和。

有向图游戏的和的 S G SG SG函数值等于它包含的各个子游戏 S G SG SG函数值的异或和，即：

S G ( G ) = S G ( G i ) ⊕ S G ( G 2 ) ⊕ ⋯ ⊕ S G ( G m ) SG(G)=SG(G_i)oplus SG(G_2)oplus dotsoplus SG(G_m) SG(G)=SG(Gi​)⊕SG(G2​)⊕⋯⊕SG(Gm​)

定理：

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

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

我们可以这样理解

在一个没有出边的节点上，棋子不能移动，它的 S G SG SG值为 0 0 0，对应必败局面。

若一个节点的某个后继节点 S G SG SG值为 0 0 0，在 m e x mex mex运算后，该节点的 S G SG SG值大于 0 0 0。这等价于，若一个局面的后继局面中存在必败局面，则当前局面为必胜局面。

若一个节点的后继节点 S G SG SG值均不为 0 0 0，在 m e x mex mex运算后，该节点的 S G SG SG值为 0 0 0

这等价于，若一个局面的后继局面全部为必胜局面，则当前局面为必败局面。

对于若干个有向图游戏的和，其证明方法与 N I M NIM NIM博弈类似。

PS:最优策略指的就是状态一定会像我们上面说的那样转换

例题：集合- N I M NIM NIM游戏

（待更。。。

#include 
#include 
#include 
#include 
using namespace std;

const int N = 110, M = 10010;
int s[N], f[M];//分别存集合S（每次能取走的数量），此状态是否被更新过
int n, k;

int sg(int x)
{
    if (f[x] != -1) return f[x];
    unordered_setS;
    for (int i = 0; i < k; 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()
{
    memset(f, -1, sizeof f);//?
    cin >> k;
    for (int i = 0; i < k; i++)
        cin >> s[i];
    cin >> n;
    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;
}