＜个人笔记＞数论

1.快速幂

(1)求解问题：

给定 n组 ai,bi,pi求 ai^bi mod pi 的值。

(2)主要思想：任何一个数(b)，可以被 n 个 2^k 相加获得。
即 b= 2^k1 + 2^k2 + 2^k3 + … + 2^logb。

快速幂模板：

typedef long long LL;

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

逆元

（1）求解问题：对于a / b mod p的值：

将除法改为乘法； 例如 求 (A / B) %p ；在B的值非常大的情况下，B作为除数，极有可能会爆精度；除数不能太大；所以我们可以把他转化为乘法来解决；

（2）主要思想：
费马小定理：对于b^p-1（mod p） = 1 恒成立。且 逆元：b * b^-1 = 1 (mod p)
所以 b 的逆元 b^-1 为 b^p-2.
可以用快速幂来求：

b^-1^ = qmi(b,p-2,p);
1