介绍

简单概括一下情况的话就是 CSP 和 NOIP 近在眼前但是 Rosmarinus 有关数论的部分几乎全部不会……所以 Ros 痛并思痛下定决心苦学数论。

也是因为前段时间在 Luogu 里发帖求资料下面只有一堆铜球所以干脆自己写一个。

这里的内容会随着 Ros 的学习进度不断更新,虽说主要是给自己看的但是我也会尽量让大家都能看懂(请相信我的教学水平),所以这是一个造福社会的东西。

前面的内容可能会比较简单。

目录

  • 同余
  • 逆元
  • 质数
  • 约数
  • 欧拉函数
  • 欧拉定理
  • 快速幂
  • 裴蜀定理
  • 扩展欧几里得算法
  • 中国剩余定理
  • 组合数
  • 卢卡斯定理

感谢名单

感谢来自 @Sya_Resory、@dengziyue、@GuidingStar、@lzxxzl 等大佬的指正。


同余

定义

对于类似于 ab(modm)a\equiv b\pmod{m} 的式子为同余方程,读作「aabb 在模 mm 意义下同余」。

含义

ab(modm)a\equiv b\pmod{m} 表示 amodm=bmodma\bmod m=b\bmod m,在 C++ 中可以表示为 a % m == b % m

性质

  • 反身性:aa(modm)a\equiv a\pmod m

  • 对称性:若 ab(modm)a\equiv b\pmod{m},则 ba(modm)b\equiv a\pmod{m}

  • 传递性:若 ab(modm)a\equiv b\pmod{m}bc(modm)b\equiv c\pmod{m},则 ac(modm)a\equiv c\pmod{m}

  • 相加:若 ab(modm)a\equiv b\pmod{m}cd(modm)c\equiv d\pmod{m},则 a±cb±d(modm)a\pm c\equiv b\pm d\pmod{m}

  • 相乘:若 ab(modm)a\equiv b\pmod{m}cd(modm)c\equiv d\pmod{m},则 acbd(modm)ac\equiv bd\pmod{m}

  • 相除:若 acbc(modm)ac\equiv bc\pmod{m},则 ab(modmgcd(c,m))a\equiv b\pmod{\frac{m}{\gcd(c,m)}}

    特殊的,若 gcd(c,m)=1\gcd(c,m)=1,则 ab(modm)a\equiv b\pmod{m}

    相对地,若 gcd(c,m)=1\gcd(c,m)=1ab(modm)a\equiv b\pmod{m},则 acbc(modm)ac\equiv bc\pmod{m}

  • 幂运算:若 ab(modm)a\equiv b\pmod{m},则 anbn(modm)a^n\equiv b^n\pmod{m}

  • ab(modmi)a\equiv b\pmod{m_i}1in1\le i\le n),则 ab(mod[m1,m2,,mn])a\equiv b\pmod{[m_1,m_2,\dots,m_n]},其中 [m1,m2,,mn][m_1,m_2,\dots,m_n] 表示 m1,m2,,mnm_1,m_2,\dots,m_n 的最小公倍数。


逆元

定义

若对于正整数 a,b,xa,b,x 满足 aba×x(modm)\frac{a}{b}\equiv a\times x\pmod{m},则称 xxbb 的逆元,记作 b1b^{-1}(注意,在这里 b1b^{-1} 不是 bb 的负一次方,b1b^{-1} 是一个整数)

性质

b×b11(modm)b\times b^{-1}\equiv 1\pmod{m}

对原式进行移项即可

求法

  • pp 是质数:

b1(modp)=bp2modpb^{-1}\pmod p=b^{p-2}\bmod p

具体证明请见「费马定理」。

  • 否则

扩展欧几里得定理。

说说我对逆元的理解

如你们所见,b1b^{-1} 在我们之前的学习中代表着 bb 的倒数,也就是 1b\frac{1}{b}

那为什么在这里又不一样了呢?

其实你可以尝试类比一下:

  • RR 中,a÷ba\div b 可以表示为 a×b1a\times b^{-1};(我不知道可不可以这么说)

但是呢?在同余系(我不知道是不是叫这个名字的)的定义域为 ZZ,也就是说是不能出现小数的。

但是啊,在同余系中,我们虽然不可以使用 a÷ba\div b,但是我们可以使用 a×b1a\times b^{-1}

所以,共同点:

  • RR 中,b×b1=1b\times b^{-1}=1
  • 在同余系中,b×b11(modp)b\times b^{-1}\equiv 1\pmod p

所以啊,逆元其实就是同余系中的除法。

提一嘴,我们的编程老师:「纯粹的除法可是一个很稀有的东西!」

所以说,当我们今后遇到一个带有除法的需要取模的式子,只要将除 aa 转化为乘 aa 的逆元即可正常操作。


质数

定义

质数和合数是针对所有大于 11 的「自然数」来定义的(所有小于等于 11 的数都不是质数)。

所有小于等于 11 的整数既不是质数也不是合数。

质数的判定——试除法:

d  nd | n 代表的含义是 nn 能被 dd 整除。(这里的 | 代表整除,在 C++ 中可以表示为 n % d == 0

一个合数的约数总是成对出现的,如果 dnd|n,那么 (n÷d)n(n\div d)|n,因此我们判断一个数是否为质数的时候,只需要判断较小的那一个数能否整除 nn 就行了,即只需枚举 d(n÷d)d\le(n\div d),即 d×dnd\times d\le ndnd\le \sqrt{n} 就行了。

sqrt(n) 这个函数执行的时候比较慢

代码:

bool is_prime(int x)
{
    if(x < 2) return false;
    for(int i = 2; i <= x / i; i ++) // x / i 是最快且最不容易爆炸的写法
    {
        if(x % i == 0) return false;
    }
    return true;
}

分解质因数——试除法(算数基本定理)

算数基本定理:任何一个大于 11 的自然数 nn,如果 nn 不为质数,那么 nn 可以唯一分解成有限个质数的乘积 n=P1a1P2a2P3a3Pkakn=P_1^{a_1}P^{a_2}_2P^{a_3}_3\dots P^{a_k}_k,这里 P1<P2<P3<<PkP_1<P_2<P_3<\dots <P_k 均为质数,其中指数 aia_i 是正整数。

特别要注意——分解质因数与质因数不一样,分解质因数是一个过程,而质因数是一个数。

一个合数分解而成的质因数最多只包含一个大于 n\sqrt{n} 的质因数。(反证法,若 nn 可以被分解成两个大于 n\sqrt{n} 的质因数,则这两个质因数相乘的结果大于 nn,与事实矛盾)

当枚举到某一个数 ii 的时候,nn 的因子里面已经不包含 [2,i1][2,i−1] 里面的数(已经被除干净了),如果 nin | i,则 ii 的因子里面也已经不包含 [2,i1][2,i−1] 里面的数,因此每次枚举的数都是质数。

质因子(质因数)在数论里是指能整除给定正整数的质数。根据算术基本定理,不考虑排列顺序的情况下,每个正整数都能够以唯一的方式表示成它的质因数的乘积。

两个没有共同质因子的正整数称为互质。因为 11 没有质因子,11 与任何正整数(包括 11 本身)都是互质。

只有一个质因子的正整数为质数。

代码:

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; // 大于sqrt(n)的数
    cout << endl;
}

筛质数(朴素筛法)

步骤:把 [2,n1][2,n−1] 中的所有的数的倍数都标记上,最后没有被标记的数就是质数。

原理:假定有一个数 pp 未被 [2,p1][2,p−1] 中的数标记过,那么说明,不存在 [2,p1][2,p−1] 中的任何一个数的倍数是 pp,也就是说 [2,p1][2,p−1] 中不存在 pp 的约数,因此,根据质数的定义可知:pp 是质数。

调和级数:当 nn 趋近于正无穷的时候,$\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\dots+\frac{1}{n}=\ln n+c$(cc 是欧拉常数,约等于 0.5770.577 左右)

时间复杂度:约为 O(nlogn)O(n\log n)(注:此处的 log\log 特指以 22 为底)

埃氏筛(稍加优化版的筛法)

质数定理:1n1\sim n 中有 nlnnn\ln n个质数。

步骤:在朴素筛法的过程中只用质数项去筛。

时间复杂度:O(nlog(logn))O(n\log(\log 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;
    }
}

线性筛

n106n\approx10^6,线性筛和埃氏筛的时间效率差不多,若 n107n\approx10^7,线性筛会比埃氏筛快了大概一倍。

核心:1n1\sim n 内的合数 pp 只会被其最小质因子筛掉。(算数基本定理)

原理:1n1\sim n 之内的任何一个合数一定会被筛掉,而且筛的时候只用最小质因子来筛,然后每一个数都只有一个最小质因子,因此每个数都只会被筛一次,因此线性筛法是线性的。

枚举到 ii 的最小质因子的时候就会停下来,即 if(i % primes[j] == 0) break;

i % primes[j] != 0 时,primes[j] 一定小于 ii 的最小质因子,primes[j] 一定是 primes[j]*i 的最小质因子。 当 i % primes[j] == 0 时,primes[j] 一定是 ii 的最小质因子,而 primes[j] 又是 primes[j] 的最小质因子,因此 primes[j]primes[j]*i 的最小质因子。

代码

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;
        // j < cnt 不必要,因为 primes[cnt - 1] = 当前最大质数
        // 如果 i 不是质数,肯定会在中间就 break 掉
        // 如果 i 是质数,那么 primes[cnt - 1] = i,也保证了 j < cnt
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

约数

试除法求所有约数

代码

int divisors[N], cnt; // divisors[] 存储所有约数

void get_divisors(int x)
{
    for(int i = 1; i <= x / i; i ++)
    {
        if(x % i == 0)
        {
            divisors[++ cnt] = i; // 约数总是成对出现
            if(i * i != n) divisors[++ cnt] = n / i; // 需要判断是否重复
        }
    }
}

求一个数所有的约数个数

公式

n=P1a1P2a2P3a3Pkakn=P_1^{a_1}P^{a_2}_2P^{a_3}_3\dots P^{a_k}_k,则 nn 的约数个数为 (a1+1)(a2+1)(a3+1)(ak+1)(a_1+1)(a_2+1)(a_3+1)\dots(a_k+1)

  • 证明

    对于任意一个 nn 的约数 mmm=P1b1P2b2P3b3Pkbkm=P_1^{b_1}P^{b_2}_2P^{b_3}_3\dots P^{b_k}_k0biai0\le b_i\le a_i 均成立,因此 mm 的个数就是 bib_i 的所有可能的取法的个数,且 bib_i 的不同取法对应的 mm 均不相同。

小知识

int 范围内,约数个数最多的数的约数个数约为 15001500 个。

代码

const int MOD = 1e9 + 7;

void get_divisors_num(int x) // 求 x 的约数个数
{
    unordered_map<int, int>primes;
    
    for(int i = 2; i <= x / i; i ++)
    {
        while(x % i == 0)
        {
            primes[i] ++;
            x /= i;
        }
    }
    if(x > 1) primes[x] ++;

    long long ans = 1;
    for(auto prime : primes) ans = ans * (prime.second + 1) % MOD; // 一个神奇的能够遍历 map 中所有元素的写法
    cout << ans << endl;
}

求一个数所有约数的和

公式

n=P1a1P2a2P3a3Pnann=P_1^{a_1}P^{a_2}_2P^{a_3}_3\dots P^{a_n}_n,则 nn 的所有约数的和为

$$(P_1^{0}+P_1^1+P_1^2+\dots+P_1^{a_1})(P_2^{0}+P_2^1+P_2^2+\dots+P_2^{a_2})\dots(P_k^{0}+P_k^1+P_k^2+\dots+P_k^{a_k}) $$

代码

const int MOD = 1e9 + 7;

void get_divisors_sum(int x) // 求 x 的所有约数的和
{
    unordered_map<int, int>primes;

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

    long long ans = 1;
    for(auto prime : primes)
    {
        int p = prime.first, a = prime.second;
        long long t = 1;
        for(int i = 1; i <= a; i ++) t = (t * p + 1) % MOD; // 为什么可以这么写,自己证吧
        ans = ans * t % MOD;
    }
    cout << ans << endl;
}

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

小性质 1

dad | adbd | b,则 d(a+b)d|(a+b)d(ax+by)d|(ax+by)。不证。

小性质 2

gcd(a,b)=gcd(b,amodb)\gcd(a,b)=\gcd(b,a\bmod b)

  • 证明

    amodb=aab×ba\bmod b=a-\lfloor \frac{a}{b}\rfloor\times b

    c=abc=\lfloor \frac{a}{b}\rfloor,则有 amodb=ac×ba\bmod b=a-c\times b

    (a,b)(a,b) 的任意一个公约数为 xx,即 xax|axbx|b

    xb\therefore x|bxax|ax(c×b)x|(c\times b)

    a>c×b\because a>c\times b

    x(ac×b)\therefore x|(a-c\times b)

    (a,b)\therefore (a,b) 的任意一公约数,都是 (b,ac×b)(b,a-c\times b) 的公约数,即左右两者等价;

    gcd(a,b)=gcd(b,ac×b)\therefore \gcd(a,b)=\gcd(b,a-c\times b)

    即:gcd(a,b)=gcd(b,amodb)\gcd(a,b)=\gcd(b,a\bmod b)

    证毕。

代码

int gcd(int a, int b) // 求 a, b 的最大公约数
{
    return b ? gcd(b, a % b) : a;
} 

欧拉函数

定义

φ(n)\varphi(n) 表示 1n1\sim n 中与 nn 互质的数的个数。

φ(6)=2\varphi(6)=2,分别为 1,51,5

特别的,φ(1)=1\varphi(1)=1

公式

n=P1a1P2a2P3a3Pkakn=P_1^{a_1}P_2^{a_2}P_3^{a_3}\dots P_k^{a_k},则 $\varphi(n)=n(1-\frac{1}{P_i})(1-\frac{1}{P_2})(1-\frac{1}{P_3})\dots(1-\frac{1}{P_k})$。

证明

已知:

  • φ\varphi 为积性函数,即若 gcd(a,b)=1\gcd(a,b)=1φ(a×b)=φ(a)×φ(b)\varphi(a\times b)=\varphi(a)\times\varphi(b)

    不会证,记结论吧。

  • 对于任意一质数 ppφ(p)=p1\varphi(p)=p-1

    由质数的定义可得。

  • 对于任意一质数 pp,$\varphi(p^a)=p^a-\frac{p^a}{p}=p^a-p^{a-1}=p^a(1-\frac{1}{p})$ ;

    由于 pp 是质数,所以 pap^a 只有 pp 一个质因数,则在 1pa1\sim p^a 的范围内,只有 p,2p,3p,,papp,2p,3p,\dots,\frac{p^a}{p}pa1p^{a-1} 个数与 pap^a 不互质。因此,根据定义得,φ(pa)=papap=pa(11p)\varphi(p^a)=p^a-\frac{p^a}{p}=p^a(1-\frac{1}{p})

因此,对于 n=P1a1P2a2Pkakn=P_1^{a_1}P_2^{a_2}\dots P_k^{a_k}

$$\varphi(n)=\varphi(p_1^{a_1})\varphi(p_2^{a_2})\dots\varphi(p_k^{a_k})=P_1^{a_1}(1-\frac{1}{P_1})P_2^{a_2}(1-\frac{1}{P_2})\dots P_k^{a_k}(1-\frac{1}{P_k})=n(1-\frac{1}{P_i})(1-\frac{1}{P_2})\dots(1-\frac{1}{P_k}) $$

证毕。

代码

void get_phi(int x) // 求 phi(x)
{
    if(x == 1)
    {
        cout << "1\n";
        return;
    }
    
    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);
    
    cout << res << endl;
}

线性筛

欧拉函数线性筛能够在 O(n)O(n) 的时间内求出 φ(1)φ(n)\varphi(1)\sim \varphi(n)

代码仅仅是在线性筛筛质数的情况下增加了几句话。

先上代码

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

void get_phi(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[i * primes[j]] = phi[i] * primes[j]; // 注释 1
                break;
            }
            phi[i * primes[j]] = phi[i] * (primes[j] - 1); // 注释 2
        }
    }
}
  • 注释 11

    primes[j] 的值为 pp,显然 pp 为质数。

    则在 i % primes[j] == 0 时,即 pip|i,此时,iii×pi\times p 的质因数完全相同。

    由于 φ(n)\varphi(n) 仅与 nn 的质因数本身,与 nn 的质因数次数无关,因此 φ(i×p)=φ(i)×p\varphi(i\times p)=\varphi(i)\times p(用言语完全无法表述清楚,请读者自行思考)。

  • 注释 22

    primes[j] 的值为 pp,显然 pp 为质数。

    则在此时,gcd(i,p)=1\gcd(i,p)=1,即 i,pi,p 互质。

    根据积性函数定义,$\varphi(i\times p)=\varphi(i)\times \varphi(p)=\varphi(i)\times(p-1)$。


欧拉定理

内容

gcd(a,n)=1\gcd(a,n)=1,即 aann 互质,则 aφ(n)1(modn)a^{\varphi(n)} \equiv 1\pmod{n}

证明

设在 1n1\sim n 中,所有与 nn 互质的数分别为 x1,x2,,xφ(n)x_1,x_2,\dots, x_{\varphi(n)}

则在 ax1,ax2,,axφ(n)ax_1,ax_2,\dots,ax_{\varphi(n)} 中,不存在 axiax_iaxjax_jaxiaxj(modn)ax_i\equiv ax_j\pmod{n}

  • 证明:

    若存在 axiaxj(modn)ax_i\equiv ax_j\pmod{n},则 a(xixj)0(modn)a(x_i-x_j)\equiv 0\pmod{n};(同余性质)

    由于 gcd(a,n)=1\gcd(a,n)=1,故 xixj0(modn)x_i-x_j\equiv 0\pmod{n}

    xixj(modn)x_i\equiv x_j\pmod{n}

    xi=xjx_i=x_j

    与现实矛盾。

    故不存在 axiaxj(modn)ax_i\equiv ax_j\pmod{n},即 ax1,ax2,,axφ(n)ax_1,ax_2,\dots,ax_{\varphi(n)} 在模 mm 意义下互不相同。

因此,x1,x2,,xφ(n)x_1,x_2,\dots, x_{\varphi(n)}ax1,ax2,,axφ(n)ax_1,ax_2,\dots,ax_{\varphi(n)} 在模 mm 意义下为顺序不同的同一组数;

因此,$a^{\varphi(n)}\times x_1x_2\dots x_{\varphi(n)}\equiv x_1x_2\dots x_{\varphi(n)}\pmod{n}$;

因此,aφ(n)1(modn)a^{\varphi(n)}\equiv 1\pmod{n}


快速幂

虽然这个应该不算数论但是应该也问题不大吧?

前置知识

ax1×ax2=ax1+x2a^{x1}\times a^{x2}=a^{x_1+x_2}(初中数学)

思路

对于 aba^bbb 是一个很大的数),将 bb 转化为二进制,即 b=2x1+2x2++2xkb=2^{x_1}+2^{x_2}+\dots+2^{x_k},我们只需要算出 a2x1a2x2a2xka^{2^{x_1}}a^{2^{x_2}}\dots a^{2^{x_k}} 即可。

时间复杂度:O(logn)O(\log n)

代码

const long long N = 1e9 + 7;
void quick_mi(long long a, long long b) // 求 a ^ b % MOd
{
    long long t = a, ans = 1;
    
    while(b)
    {
        if(b % 2 == 1) ans = ans * t % MOD; // b & 1 即为 b % 2 == 1,但是速度会快一点
        t = t * t % MOD;
        b /= 2;
    }
    
    cout << ans % MOD << endl;
}

例题:快速幂求逆元

题目描述

给定 b,pb,p,其中 pp 是质数,求 bb 在模 pp 意义下的乘法逆元。

前置知识

费马定理:若 gcd(b,p)=1\gcd(b,p)=1,则 bp11(modp)b^{p-1}\equiv 1\pmod{p}

具体做法

由于 pp 为质数,因此:

  • pbp|b,则一定不存在逆元;
  • 否则,gcd(b,p)=1\gcd(b,p)=1

因此,bp11(modp)b^{p-1}\equiv 1\pmod{p},即 b×bp21(modp)b\times b^{p-2}\equiv 1\pmod{p}

因此,bp2modpb^{p-2}\bmod p 即为我们要求的逆元。

代码

略。


裴蜀定理

对于任意一对正整数 a,ba,b,一定存在非零整数 x,yx,y 满足 ax+by=gcd(a,b)ax+by=\gcd(a,b),同时 gcd(a,b)\gcd(a,b) 是满足条件的 ax+byax+by 的最小正整数和。

  • 证明

    ax+by=dax+by=ddN+d\in N^{+}gcd(a,b)d\gcd(a,b)|d

    • 证明:由于 gcd(a,b)a\gcd(a,b)|agcd(a,b)b\gcd(a,b)|b,因此 gcd(a,b)ax+by\gcd(a,b)|ax+by,即 gcd(a,b)d\gcd(a,b)|d

    因此,gcd(a,b)\gcd(a,b) 一定是最小正整数和。

    关于存在性证明请见扩展欧几里得算法。


扩展欧几里得算法

本体

直接上代码:

int exgcd(int a, int b, int &x, int &y) // 求出 ax + by = gcd(a, b) 的一组可行解
{
    if(!b)
    {
        x = 1, y = 0; // 当 b = 0 时,显然 x = 1, y = 0 就是一组可行解
        return a;
    }
    
    int d = exgcd(b, a % b, y, x); // 注释 1
    y -= a / b * x;
    
    return d;
}

注释 1

因为 a,ba,b 翻转了所以我们把 x,yx,y 也翻转一下;

在此次递归结束后,应当有:by+(amodb)x=dby+(a\bmod b)x=d

即为: by+(aabb)x=dby+(a-\lfloor\frac{a}{b}\rfloor b)x=d

又为:ax+b(yabx)=dax+b(y-\lfloor\frac{a}{b}\rfloor x) = d

因此,令 y=yabxy=y-\lfloor\frac{a}{b}\rfloor x,就又回到了原来的式子:ax+by=dax+by=d

一直递归即可求出最终解。

此时返回的 x,yx,y 只是一组解,若要求通解,则令 t=bgcd(a,b)t=\frac{b}{\gcd(a,b)},则 xx 的通解为 x+ktx+kt,则 xx 的最小正整数解即为 (xmodt+t)modt(x\bmod t + t)\bmod t

关于裴蜀定理

由以上代码得,一定能返回一组可行解。

因此,裴蜀定理成立。

而对于 ax+by=dax+by=d,有解的充要条件为 gcd(a,b)d\gcd(a,b)|d

例题:线性同余方程

题目描述

给定正整数 a,b,ma,b,m,求出一个 xx 满足 axb(modm)ax\equiv b\pmod{m}

思路分析

对式子做一些变形:

yZ\exist y\in Z,使得 ax=my+bax=my+b

即为:axmy=bax-my=b

y=yy'=-y,则 ax+my=bax+my'=b

有解的充要条件为:gcd(a,m)b\gcd(a,m)|b

代码

略。


中国剩余定理

内容

给定 kk两两互质的整数 m1,m2,,mkm_1,m_2,\dots,m_k,我们需要解决如下线性同余方程组:

$\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\\dots\\x\equiv a_k\pmod{m_k}\end{cases}$

M=m1m2mkM=m_1m_2\dots m_kMi=MmiM_i=\frac{M}{m_i}Mi1M_i^{-1} 表示 MiM_i 在模 mim_i 意义下的逆元。

则有:$x=a_1M_1M_1^{-1}+a_2M_2M_2^{-1}+\dots + a_kM_kM_K^{-1}$。

一般题目会要求输出最小的正整数解,此时输出 (xmodM+M)modM(x \bmod M + M)\bmod M 即可。

证明

暂时不会。

先挖个坑。


组合数

定义

Cab=a!b!(ab)!C_a^b=\dfrac{a!}{b!(a-b)!}

表示在 aa 个数中取 bb 个数的方案数。

公式

Cab=Ca1b+Ca1b1C_a^b=C_{a-1}^b+C_{a-1}^{b-1}

证明

可以换个角度证明,若我们在做一道题目,用 dpi,jdp_{i,j} 表示从 ii 个苹果中取 jj 个的方案数,稍微思考一下就可以推出:dpi,j=dpi1,j+dpi1,j1dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}。都在学数论了这个应该能明白。

例题

题目描述

给定 TT1T1051\le T\le 10^5)组询问,每组询问给定两个正整数 a,ba,b1ba1051\le b\le a\le 10^5),求 Cabmod(109+7)C_{a}^{b}\bmod(10^9+7)

思路分析

考虑到数据范围,预处理出所有 CabC_a^b 不太现实,因此我们考虑另外一种做法:

若要求:CabmodpC_a^b\bmod p,即 a!b!(ab)!\dfrac{a!}{b!(a-b)!}

fact(i)=i!fact(i)=i!infact(i)=(i1)!infact(i)=(i^{-1})!

则 $C_a^b\bmod p=fact(a)\times infact(b)\times infact(a-b)$

factfactinfactinfact 数组可以在线性时间内预处理。

时间复杂度:O(nlogn)O(n\log n)

代码

#define LL long long
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;
int fact[N], infact[N];
int qmi(int a, int k, int p) // qmi = quick_mi,快速幂
{
    int ans = 1;
    while(k)
    {
        if(k & 1) ans = (LL)ans * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return ans;
}

void pre() // 预处理
{
    fact[0] = infact[0] = 1; // 边界
    for(int i = 1; i <= N; i ++) fact[i] = (LL)fact[i - 1] * i % MOD;
    for(int i = 1; i <= N; i ++) infact[i] = (LL)infact[i - 1] * qmi(i, MOD - 2, MOD) % MOD; // 费马定理
}

void Work()
{
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d\n", (LL)fact[a] * infact[a - b] % MOD * infact[b] % MOD);
}

int main()
{
    int T;
    pre();
    scanf("%d", &T);
    while(T --) Work();
    return 0;
}

卢卡斯定理

内容

对于非负整数 a,ba,b 和质数 pp 都有:$C_a^b\equiv C_{a\bmod p}^{b\bmod p}\times C_{\lfloor a\div p\rfloor}^{\lfloor b\div p\rfloor}\pmod{p}$

证明非常麻烦,建议直接记结论,若有需要请自行百度。

或者等我闲下来之后回来更新。

例题

题目描述

给定三个正整数 a,b,pa,b,p1a,b10181\le a,b\le 10^{18}1p1051\le p\le 10^5),其中 pp 是质数,求 CabmodpC_a^b\bmod p

思路分析

显然不能直接算。

考虑到 pp 不大,因此可以直接上卢卡斯定理。

时间复杂度:O(plogp)O(p\log p)

代码

#define LL long long

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

int C(int a, int b, int p) // 求组合数
{
    if(b > a) return 0; // 边界条件
    int ans = 1;
    for(int i = 1, j = a; i <= b; i ++, j --) // 因为 a,b 不会超过 p 因此直接对着原始公式爆算即可
    {
        ans = (LL)ans * j % p;
        ans = (LL)ans * qmi(i, p - 2, p) % p; // 为什么要乘逆元你们懂得吧?
    }
    return ans;
}

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

卡特兰数

定义

对于类似于:可以将长度为 nn 的问题分解成长度为 x,nxx,n-x1<x<n1<x<n)的两个子问题的问题都可以使用卡特兰数求解。

这也就是原始公式:h(n+1)=C0Cn+C1Cn1CnC0h(n+1)=C_0C_n+C_1C_{n-1}\dots C_nC_0 的由来。

公式

h(n)=C2nnn+1h(n)=\dfrac{C_{2n}^n}{n+1}

9 comments

  • 1