• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

乘法逆元和求法

需要把数论的基础知识补上。

开始之前

模运算:余数运算,如\(a\bmod b\)是将\(a \)除以\(b\)得到的余数。

性质:在加减乘除过程中,余数运算不会影响结果。

优先级:剩余操作的优先级与乘法、除法,相同,但高于加减法.

同余(这个比较重要):对于整数\(m\),如果整数\(a,b\)满足\((a-b) \bmod m=0\),即,\((a-b) \div m\)是整数值,则称为整数 \(a\) 与 \(b\) 对模 \(m\) 同余.

互质:表示两个数的最大公约数是\(1\),表示为\((x,y)=1\)

问题背景

为了求解\(\dfrac{a}{b} \bmod p\)的值,引入了逆元,因为\(a,b\)不能取模然后整除。

逆元可以理解为\(\bmod p\)意义上的\(b\)的倒数。

假设\(inv_b\)是\(b\)的倒数,则有$ $ inv _ b \ timesb \ equi v1 \ pmod { p } $ $

即,\(\ left(inv _ b-1 \ right)\ bmod p=0 \)

性质

第一个性质

\[\ dfrac { a } { b } \ equiv a \ times inv _ b \ pmod { p }

\]

证明:

\[\因为b \乘以inv_b \equiv 1 \pmod{p}

\]

\[\因此\左(b \乘以inv _ b-1 \右)\bmod p=0

\]

\[\因为x \ bmod p=x \乘以y \bmod p

\]

\[\因此\ dfrac { a } { b } \ times(b \ times inv _ b-1)\ b mod p=0

\]

\[\因此(a \ times inv _ b-\ dfrac { a } { b })\ b mod p=0

\]

\[\因此\ dfrac { a } { b } \ equiv a \ times inv _ b \ pmod { p }

\]

获得证书。

唯一性

性质

每个数字的倒数都是唯一的。

证明

假设\(b\)有两个逆元素\(x,y\)。

可以知道\(a \ times x \ equiv a \ times y \ pmod { p } \)

\[\因此\左(a \ times \左(x-y \右)\右)\bmod p=0

\]

\[\因为a \bmod p \ne 0

\]

\[\因此x=y

\]

所以每个数字的逆元唯一

逆元求法:

快速幂

这种做法是基于费马小定理:

若\(p\)为素数,\(a\)为正,且\((a,p)=1\),则有\ (a {p-1} \ equiv1 \ pmod {p} \)。

根据逆元\(inv _ a \乘以a \equiv 1 \pmod{p}\)的定义,我们可以知道:$ $\因为inv _ a \乘以a \ equiv a {p-1} \ pmod {p} $ $

\[\因此inv_a \equiv a^{p-2} \pmod{p}

\]

也就是说,一个数\(i\)在模\(p\)意义下的逆是\ (i {p-2} \ bmod p \)。

用快速幂计算就行了。

int x,p;

int ksm(int a,int b){int s=1,t=a;while(b){ if(B1)s=(s * t)% p;t=(t * t)% p;b=1;} return s;}

int main(){ cinxp;coutksm(x,p-2)endl;}

剩下的要咕咕咕了,CF 马上要开始了……

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now