引理:

缩系:

简单的定义:对于m(m>1),在 [1,m] 区间中所有与 m 互素的数可以构成一个缩系。
缩系性质 1、缩系中必定每个元素都有自己唯一的逆元,并且每个元素的逆元不与其他元素的重复 (一一对应的关系)。
缩系性质 2、对于任意的与 n 互质的正整数 k,若 {A1,A2,…,Am} 为模 n 的一个缩系,(k,n)=1, 则 {kA1,kA2,…,kAm} 也为模 n 的一个缩系 .
缩系性质 3、由缩系性质1导出:$\Pi A_i = 1$

逆元的定义:

在 mod p 意义下,若 ab=1,那么 ab 互为对方的逆元。
定理一:在 mod p(p 为质数) 意义下,任意一个数 x(1<=x< p) 都有它的逆元
证明:首先 {1,2,…,p-1} 是一个缩系。(显然)
由缩系性质1:定理1成立。
定理二:在 mod q(q 不是质数) 意义下,如果 (a,q)==1(a 在 mod q 的缩系内),a 有逆元。如果 (a,q)!=1, 那么 a 没有逆元
证明:(显然)
定理三:在 mod p 意义下,如果 ab=1, 那么 x/a=xb;
证明:因为 ab=1, 所以 1/a=b,所以 x(1/a)=xb

所以,如果 p 为质数,我们就可以放心地求 p 以内所有数的逆元。


逆元求法1:扩展欧几里德算法 (ap 互质)(lnn)

由于逆元的定义:xa=1(mod p)
所以我们可以用扩展欧几里德算法求出使 ax=1 的 x,xa+yp=1

int exgcd(int a, int b, int &x, int &y)//扩展 gcd
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int r = exgcd(b, a % b, x, y);
    int t = x % mod;
    x = y % mod;
    y = ((t - a / b * y) % mod + mod) % mod;
    return r;
}
int main()
{
    int a,inv,nt;
    cin>>a>>mod;
    exgcd(a,mod,inv,nt);
    cout<<inv<<endl;
}

逆元求法2:费马定理 (p 为质数,xp 互素)(logn)

费马定理:$x^{(p-1)}=1(mod p)$
证明:这里需要应用缩系的性质2、3。
令 $$s=x^{(p-1)}(p-1)!$$
那么 $$s=1x\times(2x)\times(3x)\times…\times((p-1)x)$$
由缩系性质 2: 这也是一个缩系的所有元素的积。因此 $s=1$
因为 (p-1)! 是一个缩系的所有元素的积,所以 (p-1)!=1
因此可以说明 $x^{(p-1)}$也为1时 s 才为1。
证毕

int ksm(int a,int mi)//快速幂
{
    int ans=1,t=a;
    while(mi>=1)
    {
        if(mi&1)ans*=t,ans%=mod;
        t*=t,t%=mod,mi/=2;
    }
    return ans;
}
int main()
{
    int a;
    cin>>a>>mod;
    cout<<ksm(a,mod-2);
}

逆元求法3:欧拉函数 (ap 互质)(sqrt(n))

欧拉定理:$a^{phi(p)} = 1 (mod p)$
证明:令 S 为 mod p 意义下缩系的元素之积,因此 S=1
那么:$a^{phi(p)}S=1$
证毕

int main()
{
    int a,mod;
    cin>>a>>mod;
    cout<<ksm(a,phi(mod)-1)<<endl;
}

逆元求法4:线性递推 (p 为质数)(平均每个 O(1))

首先证明 $i^{-1}=(pmod i)^{-1}(p-[\frac{p}{i}])$
证明:
$$p mod i = p – [\frac{p}{i}]i$$
$$p mod i = -[\frac{p}{i}]i$$
由于 $x/a=xa^{-1}$(其中 a^{-1} 为 a 的逆元),所以我们经过移项得:
$$i^{-1}=-[\frac{p}{i}](p mod i)^{-1}$$
也就是:
$$i^{-1}=(p-[\frac{p}{i}])(p mod i)^{-1}$$


int inv[1000];

int main()
{
    int p;
    cin>>p;
    inv[1]=1;
    for(int i=2;i<p;i++)inv[i]=inv[p%i]*(p-p/i)%p;
}
分类: 文章

9 条评论

litble · 2017年7月22日 7:45 下午

又打错了!!!!
$\frac{a}{b} \% c=\frac{a \% (b * c)}{b} $

    boshi · 2017年7月23日 10:50 上午

    这个呀。。。应该是你觉得该用了就可以用了吧

      litble · 2017年7月23日 1:03 下午

      什么鬼。。。
      如果这个方法随时可以用的话我们还要那么多求逆元的方法干什么。。。

        boshi · 2017年7月23日 2:17 下午

        这个呀。。。你不觉得·随时除会除出小数吗? 所以也许是装逼用的吧。比如你可以写这样的代码:

        int div(int x,int y,int c)
        {
          if(第一次使用 x)return x%(y*c)/y;
          else return x*ksm(y,c-2,c);
        }
        

litble · 2017年7月22日 7:44 下午

大佬大佬,问一下我在别的大佬的博客里看到了这个:
$\frac{a}{b} \% c=\frac{a \% (b/c)}{b}
请问这个是在哪些条件下可以用的呢?

tense · 2017年7月20日 3:56 下午

第二个 和第三个 phi(p)=p-1 ..

tense · 2017年7月20日 3:41 下午

费马定理 (p 为质数,ap 互素) 这里哪有 a 啊。。

    boshi · 2017年7月21日 8:30 上午

    下文里有蛤

    boshi · 2017年7月21日 8:31 上午

    哦哦哦是 x

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注