引理:

缩系:

简单的定义:对于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

发表评论

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

你是机器人吗? =。= *