同余运算和乘法逆元相关

maomao9173 · 2018-09-17 16:04:57 · 个人记录

同余：符号为≡，代表的运算含义如下：

nX≡m(mod p) 即等价于nX mod p == m
在一个简化剩余系中，加减乘除运算关于mod p封闭。（即新运算出来的数一定依然在原集合中。）

关于同余运算的重要定理：

欧拉定理：若正整数a,n互质，在a^φ(n)≡1 (mod n)
- 证明：设n的简化剩余系为{a1,a2...an}。对任意ai,aj，若a*ai≡a*aj，则a*(ai-aj)≡0，由于ai，aj均为质数，所以此情况出现当且仅当ai=aj。所以对于任意a*(ai-aj)!≡0，a*ai和a*aj都属于不同的同余类。
- 又因为与n互质的数构成了n的简化剩余系，所以可知：a*ai!≡a*aj，且 a*ai,a*aj∈原剩余系
- 综上所述，a^φ(n)*原剩余系之积≡原剩余系之积*原剩余系之积≡原剩余系，则a^φ(n)≡原剩余系之积(mod p)
- 因此 a^φ(n)≡1 (mod n)
费马小定理：若p为质数，则对于任意整数a，都有a^(p-1)≡1 (mod p)
- 无需证明。

关键记公式：a^φ(n)≡1 (mod n)，a^(p-1)≡1 (mod p)

费马小定理的推论：对一个任意正整数a，其乘法逆元为a^(p-2)。

Because a\*a^(p-2)≡1 (mod p)

p.s.模p运算下，乘方的次数同样可以mod p。

几个重要的乘法逆元算法

扩展欧几里得(exgcd)算法

原理：ax+by=gcd(a,b)一定有正整数解
使用：解乘法逆元
实现：逐层缩小a,b的范围，直到求出一个确切解。将确切解回代求出上层解直至完成初始解。

复杂度：单次O(logn);

int exgcd(int num_1,int num_2,int &sol_1,int &sol_2){
if(num_2==0){
sol_1=1,sol_2=0;
return num_1;//底层求解 
}
printf("solve:%3dsol_1+%3dsol_2=gcd(%3d,%3d)\n",num_1,num_2,num_1,num_2);//输出中间值 
int div=exgcd(num_2,num_1%num_2,sol_1,sol_2);//向下递归 
//  cout<<" ans: "<<"x="<<x<<" y="<<y<<endl;
int tmp=sol_1;sol_1=sol_2,sol_2=tmp-sol_2*(num_1/num_2);//顶层递归，退栈回代 
printf("ans: sol_1=%3d sol_2=%3d\n",sol_1,sol_2);
return div;//返回约数 
}

费马小定理算法
- 原理：a在mod p意义下的乘法逆元是a^p-2
- 没了。胡搞硬算，小心溢出。
- 复杂度：单次O(logn)，但实际测试略慢于exgcd
- 优先：相当简单

    inv[n]=__pow(n,p-2);

阶乘求解算法
- 原理：
  - fac[i]=fac[i-1]*i;
  - inv[fac[i]]*i=inv[fac[i]];
  - 则可以边推算其阶乘的逆元，边利用两个阶乘的逆元计算中间一个数的逆元。
- 适用范围：对多个连续数求解。
- 复杂度：单次O(n),均摊O(1)
- 以后可能会很有用

    fac[0]=1;
    for(register int i=1;i<=n;++i){
        fac[i]=((lint)fac[i-1]*i)%p;
    } 
    inv[n]=__pow(fac[n],p-2);//从n开始向前推
    for(register int i=n-1;i>=0;--i){
        res[i+1]=(lint)inv[i+1]*fac[i]%p;
        inv[i]=(lint)inv[i+1]*(i+1)%p;
    }

递推求解算法
- 思维难度高，适用范围窄，运行速度快，需要知识少。
- 推理：
  - 设 p=k*i+r
  - 则 k*i+r≡0 (mod p)
  - 则 -k*i≡r (mod p)
  - 则 -k*inv[i]≡inv[r] (mod p)
  - 则最终化简可得a[i]=-(p/i)*a[p%i];
- 没了。
```
inv[1]=1;puts("1");
for(register int i=2;i<=n;++i){
inv[i]=(lint)(p-p/i)*inv[p%i]%p;
printf("%d\n",inv[i]);
}
```