数论知识点

快速幂

image

求 $a^k \%P$ ，时间复杂度 $o(log(k))$

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

应用：求逆元

假如 $a/b \ ≡ \ a*x (\ mod\ n)$
称x为b的模n乘法逆元。

当n为质数时，可以用快速幂求逆元：

a / b ≡ a * x (mod n)
两边同乘b可得 a ≡ a * b * x (mod n)
即 1 ≡ b * x (mod n)
同 b * x ≡ 1 (mod n)
由费马小定理可知，当n为质数时
b ^ (n - 1) ≡ 1 (mod n)
拆一个b出来可得 b * b ^ (n - 2) ≡ 1 (mod n)
故当n为质数时，b的乘法逆元 x = b ^ (n - 2)

当n不是质数时，可以用扩展欧几里得算法求逆元：

a有逆元的充要条件是a与p互质，所以gcd(a, p) = 1
假设a的逆元为x，那么有a * x ≡ 1 (mod p)
等价：ax + py = 1
exgcd(a, p, x, y)

快速幂求逆元

LL qmi(int a, int b, int p)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}
int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, p;
        scanf("%d%d", &a, &p);
        if (a % p == 0) puts("impossible");
        else printf("%lld\n", qmi(a, p - 2, p));
    }

    return 0;
}

扩展欧几里得算法求逆元

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()
{
    cin >> n;
    while (n --)
    {
        int a, p, x, y;
        // if (a < p) swap(a, p);
        cin >>  a >> p;
        int d = exgcd(a, p, x, y);
        if (d == 1) cout << ((LL)x + p) % p << endl;//保证x是正数
        else puts("impossible");

    }
    return 0;
}

矩阵快速幂

将快速幂的元素改成矩阵即可

时间复杂度 O(logn)
注：该题矩阵快速幂的时间复杂度虽然是 O(logn)，看似能跑的飞快，但实际上还有 27的常数，并不能跑的飞快，当然过这题毫无压力


const int N = 3;

int n, m;
// c = a * b
void mul(int c[], int a[], int b[][N])
{
    int temp[N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;
    // 用temp，不能用函数传参的指针
    memcpy(c, temp, sizeof temp);
}

void mul(int c[][N], int a[][N], int b[][N])
{
    int temp[N][N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            for (int k = 0; k < N; k ++ )
                temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % m;

    memcpy(c, temp, sizeof temp);
}

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

    int f1[N] = {1, 1, 1};
    int a[N][N] = {
        {0, 1, 0},
        {1, 1, 1},
        {0, 0, 1}
    };

    n -- ;
    while (n)
    {
        if (n & 1) mul(f1, f1, a);  // res = res * a
        mul(a, a, a);  // a = a * a
        n >>= 1;
    }
    cout << f1[2] << endl;
    return 0;
}

算术基本定理

算术基本定理
所有正整数都可以分解成质因子乘积的形式，

N = P[1]^d[1] * P[2]^d[2] ... P[k]^d[k]
P[i]为质数 d[i]>0
约数个数：(d[1]+1)(d[2]+1)...*(d[k]+1)
约数之和：S = (1+p1+p1^2+…+p1d[1])(1+p2+p2^2+…+p2d[2])…(1+pn+pn^2+…+pnd[n])

应用
给一个数S，让你找到有多少数能够满足它约数的和等于S
比如S = 42
这个时候就有3个数满足条件
41 = (1 + 41) == 42
20 = (1 + 2 + 4 + 5 + 10 + 20) == 42
26 = (1 + 2 + 13 + 26) == 42
AcWing 1296. 聪明的燕姿
优化到根号n
https://www.acwing.com/solution/content/10545/

筛法求素数

线性筛

o(n) 时间内求出1~n中所有质数以及每个数的最小质因子
关键点：

筛掉的一定是合数，且用最小质因子筛的（primes[j] 一定不大于i的最小质因子）
合数是否一定会被筛掉

N = (1 << 20) + 10
primes = [0 for i in range(N)]
cnt = 0
st = [False for i in range(N)] # 当前的数有没有被筛过
minp = [0 for i in range(N)]

def get_primes(n):
    global cnt
    for i in range(2, n+1):
        if st[i] == False:
            primes[cnt] = i
            minp[i] = i
            cnt += 1
        j = 0
        while i * primes[j] <= n:
            st[i * primes[j]] = True
            minp [ i * primes[j] ] = primes[j]
            if i % primes[j] == 0:
                break
            j += 1
get_primes(N-1)      

while True:
    try:
        n = int(input())
        tot = 0
        down = 1
        up = 1
        while n > 1:
            p = minp[n]
            # print(n, p)
            i = 0
            while n % p == 0:
                i += 1
                down *= i
                tot += 1
                up *= tot
                n //= p           
        print(tot, up // down)
    except:
        break

最大公约数

AcWing 1246. 等差数列

辗转相除法

o(logn)
gcd(a,b) =gcd (b,a%b)

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

辗转相减法

时间复杂度：o(n)
gcd(a,b) = gcd(b,a-b)
主要应用：
辗转相减法可以用来求若干个形如 $( \frac{p}{q})^{r_{i}}$ 数的求 ${r_{i}}$ 最大公约数d,分子分母分开求，但返回结果为 ${p}^{d}$ 或 ${q}^{d}$ :

算法推导
$f\left(p^{x}, p^{y}\right)=p^{(x, y)}=p^{(y, x-y)}=f\left(p^{y}, p^{(x-y)}\right)=f\left(p^{y}, \frac{p^{x}}{p^{y}}\right)$

int gcd_sub(int a, int b){
    if(a < b) swap(a, b);
    if(b == 1) return a; // 此时p^y = 1即y = 0
                         // 由于0和任何正整数r的最大公约数都是r，所以此时应返回p^r，即a
    return gcd_sub(b, a / b);
}

AcWing 1223. 最大比例

卡特兰数

定义

首先看一下卡特兰数。若一个数列h $_n$ 满足：
$h_{n}=\sum_{i=0}^{n-1} h_{i} \cdot h_{n-1-i}$
则称h $_n$ 为卡特兰数列。
还有一种形式若：
$h_{n}=\frac{C_{2 n}^{n}}{n+1}$

应用

本质：任何时间以前，某种操作的个数都不少于另一种操作的个数的方法数

https://www.acwing.com/problem/content/891/

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

https://www.acwing.com/problem/content/417/

栈的出栈顺序的个数也是上述问题，可以将0看成进栈和1看成出栈。

1push 2push 3push 3pop 2pop 1pop 序列为321
1push 1pop 2push 2pop 3push 3pop 序列为123
1push 2push 2pop 1pop 3push 3pop 序列为213
1push 1pop 2push 3push 3pop 2pop 序列为132
1push 2push 2pop 3push 3pop 1pop 序列为231

证明

0代表向右走，1代表向上走，在坐标轴上转化为路径问题，合法路径不能超过y=x。

image

思想：任何一条非法路径对应一条从(0,0)到(n-1,n+1)的路径

图中橙色与紫色满足条件.
那满足条件的路线一共有多少呢?直接求不是很好求,所以我们可以转化一下,用所有的路线减去不满足条
件的路线,那不满足条件的路线有什么样的特点呢?
这样的路线上必然存在一点的纵坐标是大于横坐标的,即这样的路线一定经过了y=x＋1这条线,以图中
的褐色为例.我们将褐色的路线第一次经过y=x＋1以后的路线关于y=x＋1做轴对称,用黑色的线表
示.我们可以发现所有不满足的条件的路线都可以通过这种方式将终点变为(n-1,n＋1),在这个例子中
即为 $(5,7)$ 所有的路线为C $_1$$_2$ ,因为一共有12个空,要放6个0所以为C $_1$$_2$ ,同理:不满条件的路线为
C $_1$$_2$ .因此在本题中满足条件的路线为: $C_{12}^{6}$ （所有的路线)- $-C_{12}^{5}$ （不满足条件的路线)
所以在一般问题中即为:
$C_{2 n}^{n}-C_{2 n}^{n-1}$

$C_{2 n}^{n}-C_{2 n}^{n-1}=\frac{(2 n) !}{n ! n !}-\frac{(2 n) !}{(n-1) !(n+1) !}=\frac{(2 n) !(n+1)-(2 n) ! n}{n !(n+1) !}=\frac{(2 n) !}{n !(n+1) !}=\frac{(2 n) !}{n ! n !(n+1)}=\frac{C_{2 n}^{n}}{n+1}$