逆元

欧几里得算法

即辗转相除法，证明如下。

 

基本算法：设a=qb+r，其中a，b，q，r都是整数，则gcd(a,b)=gcd(b,r)，即gcd(a,b)=gcd(b,a%b)。

 

第一种证明：

 

a可以表示成a = kb + r，则r = a mod b

 

假设d是a,b的一个公约数，则有

 

d|a, d|b，而r = a - kb，因此d|r

 

因此d是(b,a mod b)的公约数

 

假设d 是(b,a mod b)的公约数，则

 

d | b , d |r ，但是a = kb +r

 

因此d也是(a,b)的公约数

 

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证

 

乘法逆元

乘法逆元官方定义：

群G中任意一个元素a，都在G中有唯一的逆元a‘,具有性质aa'=a'a=e，其中e为群的单位元。

然而百度百科非常人性化，它还有配套的例子！

例子如下：

 

例如：4关于1模7的乘法逆元为多少？

 

4X≡1 mod 7

 

这个方程等价于求一个X和K，满足

 

4X=7K+1

 

其中X和K都是整数。

这就很容易理解了。

如果有ax≡1(modp)，则称x是mod p意义下a的乘法逆元。

其实就是a乘一个数在什么情况下％p什么时候＝1。

改变一下形式就是ax＝pk＋1的一组解，求x即可。

通过费马小定理，可以得到一个新的算法。

即(a/b)%p=1;但是我们无法直接求1/b的值，所以我们就把b/1设成c，只须求ac%p=1即可。

费马小定理可得：b%p的逆元 = b^p-2（mod p）;

const int mod = 1000000009;
long long quickpow(long long a, long long b) {
    if (b < 0) return 0;
    long long ret = 1;
    a %= mod;
    while(b) {
        if (b & 1) ret = (ret * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ret;
}
long long inv(long long a) {
    return quickpow(a, mod - 2);
}

同样逆元可以线性求，即为积性函数求法。

代码如下

const int mod = 1000000009;
const int maxn = 10005;
int inv[maxn];
inv[1] = 1;
for(int i = 2; i < 10000; i++)
    inv[i] = inv[mod % i] * (mod - mod / i) % mod;

最近做的组合数的题，如果用杨辉三角预处理计算是n^2算法会爆，需要用阶乘和逆元分别求分母分子。

阶乘其实就是将阶乘的最后一位用费马小定理求逆元，然后按位往前求，每次乘上一位的位置即可。

代码如下

inv[maxn]=mod_pow(fac[maxn],mod-2);
for(ll i=maxn-1;i>=0;i--)
    inv[i]=(inv[i+1]*(i+1))%mod;