逆元

2019-07-25

在计算机里面为了存储数据于是我们定义了 int、long、long long、 _ _ 128、……还有小数float double long double ,但是都是有精度范围,因此催生出了大整数加减乘除的题目和求逆元的需求

大整数的题目比较入门，也是通过手动模拟就可以实现，这里不讲

逆元也比较入门，只是需要一点点基础知识（费马小定理（快速幂）或者拓展欧几里得（模的性质））

概念

逆元，这里指的是分数（小数）对某个较大整数进行取模的运算

$\frac{a}{b} \% n$

一般的取模运算，就是整数 % 整数 ,像 $ {5\%3=2} $ , $ {14 \% 5 = 4} $

而分数，小数的取模运算，比起整数来说还有点难以理解比如

${\frac{3}{4}\%1000000007=750000006}$ ${\frac{1}{1}\%1000000007=1}$

而对于分数意义下的取模运算，可以有以下理解

通俗的讲，逆元可以看做一个数的倒数的整数形式，但是一个数的逆元在不同的 $ \% $ 意义下是不一样的。

$a\times x\equiv1 \\% n → a\times \frac{1}{a}\equiv1 \\% n$

这个方程便是逆元的真正定义，$ x $ 的解即代表 $a$ 在 $ \% n $ 意义下的逆元，通俗的讲：此时的 $x$ 就相当于 $a$ 的倒数，这样 $a\times x$ 便会等于1，在 $\%n$ 意义下余数必定为一。当然这个式子要建立在 $a$ 与 $n$ 互质的基础上

可是逆元有什么用呢？直接用倒数不行吗？这是因为我们发现一个分数 $\%$ 一个整数时是不能直接模运算的，但是可以进行乘法运算，我们就要用到逆元（一个数倒数的整数形式）

就像：

$\frac{a}{b}\% n \not =\frac{a\% n}{b\% n}\% n$

但是：

$\frac{a}{b}\% n=(a\times b^{-1})\% n$

所以当除运算碰上我们的模运算时，我们就需要 $\\%$ 模数意义下的逆元了

P.S.

1.若n|(a-b)，则a≡b (% n)。例如 11 ≡ 4 (% 7)， 18 ≡ 4(% 7)
2.(a % n)=(b % n)意味a≡b (% n)
3.对称性：a≡b (% n)等价于b≡a (% n)
4.传递性：若a≡b (% n)且b≡c (% n) ，则a≡c (% n)

$\begin{array} (a + b) &\% n & = & (a \% n + b \% n) &\% n & （1）\\ (a - b) &\% n & = & (a \% n - b \% n + n ) &\% n &（2）\\ (a * b) &\% n & = & (a \% n * b \% n) &\% n &（3）\\ a ^ b &\% n & = & ((a \% n)^b) &\% n &（4）\\ \end{array}$

求法

一、拓展欧几里得求法

1.同时存在两个整数 $ x_1 $ $ y_1 $ ，使得：$ x_1 \times a + y_1 \times b = gcd(a,b) $

2.同理，同时存在两个整数 $ x_2 $ $ y_2 $ ，使得：$ x_2 \times b + y_2 \times ( a \% b) = gcd ( b , a \% b ) $

根据 gcd 的性质，上述两个等式的右半部分相同，同理它们的左半部分也相同

易得

1.$ x_1\times a+y_1\times b=x_2\times b+y_2\times (a\% b) $

2.$ x_1\times a+y_1\times b=x_2\times b+y_2\times (a-\frac{a}{b}\times b) $

3.$ x_1\times a+y_1\times b=y_2\times a+(x_2-y_2\times \frac{a}{b})\times b $

4.$ y_1=x_2-y_2\times \frac{a}{b} $

所以我们根据 $x_2$ 和 $y_2$ 就能求出 $x_1$ 和 $y_1$ 。而众所周知的， $gcd$ 的解就是 $b==0$ 的时候，这时我们的 $x=1$ ，而因为 $b==0$ ，所以我们的 $y$ 随便取一个就行（好像大多数人用0），然后我们在回溯的时候，不断往前推我们的 $x$ 和 $y$ ，直到得出我们最初的那一组解。（这其实就是一个构造的过程）

然后，我们发现只有当我们的 $a$ 与 $b$ 互质的时候即 $ gcd(a,b)=1 $ 时，这个二元一次方程变成了： $ x_1\times a+y_1\times b=1 $ （等同于 $ x_1\times a=1(\% b) $) 或 $ y_1\times b=1(\% a) $ ）而这，就相当于我们逆元的定义式.我们再用上述方法将 $x_1$ 和 $y_1$ 求出来，就是逆元

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

#include<stdio.h>
#define ll long long

ll gcd(ll a,ll b,ll &d,ll& x,ll& y){
    if(!b){
        d=a;
        x=1;
        y=0;
        return x;
    }
    else{
        gcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
    return x;
}

int main(){
    ll a,b,d,x,y;
    while(scanf("%lld%lld",&a,&b)!=EOF){
        x=gcd(a,b,d,x,y);
        printf("a:%lld->x:%lld\n",a,x);
    }
    return 0;
}

二、费马小定理求法

费马小定理如下：
若整数$a$与一个质数$n$互质，则有：

$a^{p-1} \equiv 1 (\%n)$

这就是费马小定理，看起来和逆元毫无关系，但是如果稍微修改一下：

$a \times a^{p-2} \equiv 1 (\%n)$

就可以发现和逆元的定义惊人的相似，因此快速幂上场

ll quick_multiply(ll x){//求x在%mod意义下的逆元
    int times=mod-2;ll ans=1;
    while(times){
        if(times&1)ans=ans*x%mod;
        x=x*x%mod; times>>=1;
    }
    return ans;
}