由于C++储存数据的范围是有限的,当数据超出储存范围时计算就会出错,为了避免错误,一般使用求余的方法。 $(a+b)\%c$可以表示为$(a\%c+b\%c)\%c$,乘法同理

减法也可以表示为$(a+c-b)\%c$

但是除法怎么办呢?

想一下除法计算过程:$a/b=a* 1/b$

那么自然会想到,把$(a/b)\%c$变成$(a(1/b))$不就可以了吗。
但是现实是残酷的,取余是建立在除数和被除数都算整数的基础上的,浮点数无法进行取余计算。那么我们可不可以在$1~c-1$中找到一个数x使得$(a/b)\%c==(a
x)\%c$ 呢?即$b x=1(\%c)$;
答案是肯定的!
这个x就叫做b的逆元,或者叫做数论倒数(和正常意义上的倒数不一样,但和正常意义上的倒数具有相同的作用)。
有逆元的充要条件
$a$在mod c意义下有逆元的充要条件:GCD(a,c)=1
那么*逆元
要怎么求呢?

  1. EXGCD
    求a在mod c意义下的逆元,可以转化为求 ax+cy=1 ;
    就可以用EXGCD求逆元了。
1
2
3
4
5
void ex_gcd(LL a,LL b,LL &x,LL &y){    
if(!b){x=1;y=0;return;}
ex_gcd(b,a%b,y,x);
y-=a/b*x;
}
  1. 费马小定理
    如果p为质数,则$a^{p−1}≡1\%p$
    $∴a*a^{p−2}≡1\%p$
    快速幂求$a^{p-2}$就可以啦。
1
2
3
4
5
6
7
8
9
10
11
int q_pow(int a,int n,int m) {    
int ans = 1;
while(n) {
if (n&1) {
ans = ans*a%m;
}
a = a*a%m;
n >>= 1;
}
return ans;
}
  1. 欧拉定理
    将费马小定理中的p−2换为φ( p )−1即可
    p可以不是质数
  2. 递推
    用于O(n)预处理[1⋯n]的逆元
    构造$p=k i+r$
    $∴k
    i+r≡0\%p $
    $∴k i=−r $
    $∴i−1=−k
    r−1 $
    其中$k=⌊pi⌋,r=p\%i $
    $∴i−1=−⌊pi⌋⋅inv[p\%i] $
  3. 为了防止出现负数,通常的写法是这样的
1
inv[i]=(mod-mod/i)*inv[mod%i]%mod;

参考博客:

https://blog.csdn.net/Gh0stCai/article/details/79968462 https://blog.csdn.net/Adusts/article/details/80627966

评论




博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

载入天数...载入时分秒... 本站使用 Volantis 作为主题 鲁ICP备-20012065号