在计算机里面为了存储数据于是我们定义了 int、long、long long、 _ _ 128、……还有小数float double long double ,但是都是有精度范围,因此催生出了大整数加减乘除的题目和求逆元的需求
大整数的题目比较入门,也是通过手动模拟就可以实现,这里不讲
逆元也比较入门 ,只是需要一点点基础知识(费马小定理(快速幂)或者 拓展欧几里得(模的性质))
概念
逆元,这里指的是分数(小数)对某个较大整数进行取模的运算
一般的取模运算,就是 整数 % 整数 ,像 $ {5\%3=2} $ , $ {14 \% 5 = 4} $
而分数,小数的取模运算,比起整数来说还有点难以理解 比如
而对于分数意义下的取模运算,可以有以下理解
通俗的讲,逆元可以看做一个数的倒数的整数形式,但是一个数的逆元在不同的 $ \% $ 意义下是不一样的。
这个方程便是逆元的真正定义,$ x $ 的解即代表 $a$ 在 $ \% n $ 意义下的逆元,通俗的讲:此时的 $x$ 就相当于 $a$ 的倒数,这样 $a\times x$ 便会等于1,在 $\%n$ 意义下余数必定为一。当然这个式子要建立在 $a$ 与 $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)
求法
一、拓展欧几里得求法
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$ 求出来,就是逆元1
2
3
4
5int 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;
}
1 |
|
二、费马小定理求法
费马小定理如下:
若整数$a$与一个质数$n$互质,则有 :
这就是费马小定理,看起来和逆元毫无关系,但是如果稍微修改一下:
就可以发现和逆元的定义惊人的相似,因此快速幂上场1
2
3
4
5
6
7
8ll 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;
}