…An)/(A1还是称b 是a 的乘法逆元。

 

 

图片 1

定义

乘法逆元的定义:若在正整数a,b,p, 满足ab = 1(mod p), 则称a 是b
的乘法逆元, 或称b 是a 的乘法逆元。b ≡ a-1 (mod p),a ≡
b-1 (mod p)

诸如, 在模7 意义下,3 的乘法逆元是5, 也得以说模7
意义下5的乘法逆元是3。模13意义下5的逆元是8……

图片 2

存在性

扣押起与同余方程很一般(其实下面真的可以用exgcd求的!),在跟余方程中

ab ≡ 1(mod p)

若a 与p 互质, 则一定在一个恰巧整数解b, 满足b < p,若a 与p 不互质,
则一定非有正整数解b.

于是逆元要求a与p互质

主题要求:(Ar*A2…An)%p,亦即[(A1*A2*…An)/(A1*A2*…Ar-1)]%p,由于A1*A2…An乘积过非常,无法求得相除所得的结果

求法

求逆元有三种求法,

俺们要用乘法逆元(a*k≡1 (mod
p)的k值就是a关于p的乘法逆元),而乘法逆元有如下定理®:(a*k) mod
p结果及(a/b) mod p等价,其中k为b关于p的乘法逆元

1、扩展欧几里得

得据此扩展欧几里得求,那么是怎个求法呢?

推而广之欧几里得是因此来求这样的等同组解的:ax+by =
gcd(a,b),求x和y,(求出x后当然懂得了y,所以算求一个x)。

逆元呢是告这样的一个解:ax ≡ 1 (mod
b),(为了方便清楚,改了转变量称作),求x,貌似并不曾一点点一般处,那么我们换一下,

ax+by = gcd(a,b),变成 ax+by = c;

ax ≡ 1 (mod b),变成 ax-by = 1;如果以y看成负的,ax+by = 1;

毕平等嘛,所以直接套用扩展欧几里得求即吓了。

代码

图片 3图片 4

 1 #include<cstdio>
 2 
 3 int exgcd(int a,int b,int &x,int &y)
 4 {
 5     if (b==0)
 6     {
 7         x = 1;
 8         y = 0;
 9         return a;
10     }
11     int r = exgcd(b,a%b,x,y);
12     int tmp = x;
13     x = y;
14     y = tmp-a/b*y;
15     return r;
16 }
17 
18 int main()
19 {
20     //gcd(a,p)==1
21     int a,p,r,x,y;
22     while (scanf("%d%d",&a,&p)!=EOF)
23     {
24         r = exgcd(a,p,x,y);
25         printf("%d",(x%p+p)%p);
26     }
27     return 0;
28 }

壮大欧几里得求逆元

设若鉴于费马小定理(已知p是质数且gcd(a, p) = 1,则 ap-1 ≡ 1 (mod
p),  所以 a*ap-2 ≡ 1 (mod
p))知,a^(p-2)就是a的逆元了求解,利用高效幂运算计算(补充:亦可用扩展欧几里得求解)

2、线性求逆元

事先改一下变量名叫,再变动回去ab = 1(mod p),求b

p%a = p-(p/a)*a;  在c++中/为整除。

(p/a)*a = p-(p%a);  换下位置

(p/a)*a = -(p%a);  在模p意义下p可以大体少,可以没有当即无异于步

a = -(p%a)/(p/a);  再转换一下职

a-1 = -(p%a)-1*(p/a);

所以a-1可以用(p%a)-1产,所以就好用递推式来生产1到a的所有数的逆元。

代码

图片 5图片 6

1 int inv[MAXN]; 
2 void INV(int a,int p)//线性求到a的逆元 
3 {
4     inv[1] = 1;
5     for (int i=2; i<=a; ++i)
6         inv[i] = (-(p/i))*inv[p%i]%p; 
7 }

线性求逆元1

下面的代码只请一个值的逆元,运用的凡方的架子

图片 7图片 8

1 int INV(int a)//线性求a的逆元 
2 {
3     if (a==1) return 1;
4     return ((-(p/a)*INV(p%a))%p);
5 }

线性求逆元2

瞩目具体求a时,应持续对p取mod

3、欧拉定理求逆元

欧拉定理:aφ(p) ≡ 1(mod p)

于随意互质的a,p 恒成立。

欧拉定理用来呼吁逆元用的凡欧拉定理的一个测算:
a*aφ(p)-1 ≡ 1(mod p

密切考察,a*b ≡ 1(mod
p),在此间的b不纵是端的aφ(p)-1为?,所以求出aφ(p)-1就好了。

之所以我们所以便捷幂即使可以求出乘法逆元了。

本条方式它需差不多算一个欧拉函数,代码这里不再吃来。

补充:其实如果果p是质数的言语,可以据此费马小定理,与欧拉定理是截然一样的,费马小定理在p不是质数时,则不得不用欧拉定理。

怎整也?费马小定理 a(p-1) ≡ 1(mod p)
p是质数,且a,p互质,

然后拿地方的姿态变一下,a*a(p-2) ≡ 1(mod p) ,

再次换一下,a(p-2) 
a-1 (mod p)
,然后求出a(p-2)即便可了。

接下来再次拘留一下欧拉定理,如果p是质数,φ(p) =
p-1,那么我们求aφ(p)-1,也就是求a(p-2)。和费马小定理是一致的。

#include <stdio.h>
#include <string.h>
#define LEN 100001
#define P 9973

/*注意:转化为s时,必须从1开始,因为如果a=1,那么在做快速幂时,会用到s[-1],造成下标越界*/ 
void Transform(char *s1,int *s){
    int i;
    s[0]=1;
    for(i=1;i<=strlen(s1);i++) //the entire len 
        s[i]=s[i-1]*(s1[i-1]-28)%P;
}

void HashValue(int a,int b,int *s){
    //s[b]*s[a-1]^(p-2) mod p
    //quickmod
    int res,tmp,n;
    n = P-2;
    res = 1; 
    tmp = s[a-1];//s必须从1开始取 
    while(n){
        if(n&1)
            res=(res*tmp)%P;
        n >>=1;
        tmp=(tmp*tmp)%P;
    }

    printf("%d\n",s[b]*res%P);
} 

int main(){
    int n,a,b,i,s[LEN]; 
    char s1[LEN];
    while(scanf("%d",&n)!=EOF){
        getchar();
        gets(s1);
        Transform(s1,s);
        for(i=0;i<n;i++){
            scanf("%d%d",&a,&b);
            HashValue(a,b,s);
        }
    }
    return 0;
}

应用

我们领略(a+b)%p = (a%p+b%p)%p

    (a*b)%p = (a%p)*(b%p)%p

求(a/b)%p时,可能会见因为a是一个大特别之累,不克一直算出来,也无法像上面一样说。

咱们得经求b关于p的乘法逆元k,k ≡ b-1 (mod p)
,将a乘上k再模p,即(a*k) mod p。其结果以及(a/b) mod p等价格。

接下来立即即变成了求a*k%p,然后就是得就此那片单公式了。

 

民用了解

于私有的明亮逆元,逆元是以运算除时,可以改为乘,方便计算,像上面一样,a/b(mod
p)就好变成a*b-1,这为便是逆元的原形,必须使在的意义下才有效。

运算a/b时,我们除以b就相当给随着以1/b,这是只分数,不便宜计算,所以我们就是找到了一个平头,b的逆元,比如计算12/3(mod
7),这是单除法,所以我们可以这样12*(1/3),虽然是乘法了,但是来分,所以找一个平头使得x,3x≡1(mod
7),x=5,即模7意义下3的逆元是5,然后我们乘机以这逆元,12*5 = 60,60 mod
7 = 4,诶,12/3 = 4,相等啊,这就是是端所说的特性,

 

定理 ®的证明:

由:b*k≡1 (mod p)有b*k=p*x+1,k=(p*x+1)/b
将k代入(a*k) mod p,得:
[a*(p*x+1)/b]mod p
=[(a*p*x)/b+a/b]mod p(注意:只要a整除b,自然有(a*p*x)整除b)
={[(a*p*x)/b] mod p +(a/b)} mod p
={[p*(a*x)/b]mod p +(a/b)} mod p,而p*[(a*x)/b] mod p=0

=(a/b) mod p

参考资料:

  [1]http://blog.csdn.net/nickwong\_/article/details/38797629

     
[2]http://www.cnblogs.com/tiankonguse/archive/2012/08/14/2638949.html

      [3]http://blog.csdn.net/jklongint/article/details/51415402

 Time:20:48:52 2017-03-01

相关文章