算法笔记（08）：数论初步

除法

对于两个整数 a , b ,存在两个唯一的整数 q , r 满足：

$$b= aq + r$$​

当 r = 0 时，我们称 a 整除 b , 记作 a | b， 称 a 为 b 的约数

算术基本定理

n的质因数分解唯一。

Π(n) 表示 小于等于 n的素数个数。

约定下面公式中 p 为素数

$$\displaystyle \lim_{n\rightarrow \infty} \frac{\pi(n) }{\frac{n}{\ln n}} = 1$$

$$P_n = O(n\log n)$$

$$\displaystyle \sum_{i = 1} ^ n \frac{1}{i} = O(\log n)$$

$$\displaystyle \sum_{1 \leq p \leq n} \frac{1}{p} = O(\log \log n)$$

整除性质：

$$a | c , b | c, (a,b) = 1 \rightarrow ab | c$$

$$a | bc , (a,b) = 1 \rightarrow a|c$$

$$p | ab \rightarrow p | a或 p | b$$

辗转相除法

$$(a,b) = (a - b, b)$$

$$d | a ,d | b \rightarrow d | (a-b) , d | b$$

$$d | (a,b) 等价于 d | (a-b,b)$$​

时间复杂度：log min(a,b)

特别的：

如果 a,b 都是奇数，那么 (a,b) = (a-b,b)

如果 a 是偶数，b 是奇数，那么 (a,b) = (a / 2,b)

如果 a,b 都是偶数，那么 (a,b) = 2(a / 2,b / 2)

裴蜀定理

对任意整数 a , b , d , (a , b) | d ，存在整数 u , v 使得 ua + vb = d

扩展欧几里得

$$\displaystyle a\mod b = a - \lfloor{\frac{a}{b}}\rfloor b$$

由归纳法假设存在 u’ , v’ 使得 u’ b + v’ (a mod b) = d

即

$$\displaystyle u’b + v’(a - \lfloor{\frac{a}{b}}\rfloor) b = d$$

$$\displaystyle v’a + (u’ - \lfloor{\frac{a}{b}}\rfloor v’) b = d$$

于是就有了 (a,b) 的解。

代码

int exgcd(int a,int b,int &x,int &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    // int xx,yy;
    // int d = exgcd(b,a % b,xx,yy);
    // x = yy;
    // y = xx - (a / b) * yy;

    int d = exgcd(b,a % b, y, x);
    y -= (a / b) * x;
    return d;
}