


下載本文檔
版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、求逆元基本方法乘法逆元小結(jié)乘法逆元,一般用于求$fracabpmodp$的值($p$通常為質(zhì)數(shù)),是解決模意義下分?jǐn)?shù)數(shù)值的必要手段。一、逆元定義若$a*xequiv1pmodb$,且$a$與$b$互質(zhì),那么我們就能定義:$x$為$a$的逆元,記為$aA-1$,所以我們也可以稱$x$為$a$在$modb$B義下的倒數(shù),所以對(duì)于$displaystylefracabpmodp$,我們就可以求出$b$在$bmodp$下的逆元,然后乘上$a$,再$bmodp$,就是這個(gè)分?jǐn)?shù)的值了。二、求解逆元的方式1拓展歐幾里得條件$abotp$(互質(zhì)),但$p$不是質(zhì)數(shù)的時(shí)候也可以使用。這個(gè)方法十分容易理解,而且對(duì)
2、于單個(gè)查找效率似乎也還不錯(cuò),比后面要介紹的大部分方法都要快尤其對(duì)于$bmodp$比較大的時(shí)候)。這個(gè)就是利用拓歐求解線性同余方程$a*xequivcpmodb$的$c=1$的情況。我們就可以轉(zhuǎn)化為解$a*x+b*y=1$這個(gè)方程。引理:$ax+by=c$有解的充分條件$gcd(a,b)midc$所以$ax+by=gcd(a,b)鳥(niǎo)顯然有解引理:$gcd(a,b)=gcd(b,amodb)$將$代入$得$ax_1+by_1=bx_2+(amodb)y_2$ax_1+by_1=bx_2+(a-fracab*b)y_2$ax_1+by_1=bx_2+ay-fracab*by_2$ax_1+by_1=
3、ay_2+b(x_2-fracab)$.x_1=y_2,y_1=x_2-fracaby$vabotb$.,.gcd(a,b)=1$當(dāng)b=0時(shí),a=1,此時(shí)有x=1,y的最小自然數(shù)解為0$代碼比較簡(jiǎn)單:voidExgcd(lla,llb,ll&x,ll&y)if(!b)x=1,y=0;elseExgcd(b,a%b,y,x),y-=a/b*x;intmain()llx,y;Exgcd(a,p,x,y);x=(x%p+p)%p;printf(%dn,x);/x是a在modp下的逆元2小費(fèi)爾馬定理(快速幕)費(fèi)馬小定理:若$p$為素?cái)?shù),$a$為正整數(shù),且$a$、$p$互質(zhì)。則有$aAp-1equiv1
4、(bmodp)$。這個(gè)我們就可以發(fā)現(xiàn)它這個(gè)式子右邊剛好為$1$。所以我們就可以放入原式,就可以得到:$a*xequiv1pmodp$a*xequivaAp-1pmodp$xequivaAp-2pmodp$所以我們可以用快速幕來(lái)算出$aAp-2pmodp$的值,這個(gè)數(shù)就是它的逆元了代碼也很簡(jiǎn)單:llfpm(llx,llpower,llmod)x%=mod;llans=1;for(;power;power=1,(x*=x)%=mod)if(power&1)(ans*=x)%=mod;returnans;intmain()IIx=fpm(a,p-2,p);x為a在modp意義下的逆元線性推逆元用于求
5、一連串?dāng)?shù)字對(duì)于一($bmod卩$的逆元。只能用這種方法,別的算法都比這些要求一串要慢。首先我們有一個(gè),$1A-1equiv1pmodp$然后設(shè)$p=k*i+r,(1rip)$也就是$k$是$p/i$的商,$r$是余數(shù)。再將這個(gè)式子放至U$pmodp$意義下就會(huì)得到:$k*i+requiv0pmodp$然后乘上$iA-1$,$rA-1$就可以得到:$k*rA-1+iA-1equiv0pmodp$iA-1equiv-k*rA-1pmodp$iA-1equiv-lfloorfracpirfloor*(pbmodi)A-1pmodp$于是,我們就可以從前面推出當(dāng)前的逆元了。代碼也很短:inv1=1;f
6、or(inti=2;ip;+i)invi=(p-p/i)*invp%i%p;階乘逆元$O(n)$求因?yàn)橛腥缦乱粋€(gè)遞推關(guān)系。$dispIaystyIeinvi+1=frac1(i+1)!$dispIaystyIeinvi+1*(i+1)=frac1i!=invi$所以我們可以求出$n!$的逆元,然后逆推,就可以求出$仁川$所有的逆元了。遞推式為$invi+1*(i+1)=invi$所以我們可以求出$displaystyleforalli,i!,frac1i!$的取值了。然后這個(gè)也可以導(dǎo)出$displaystylefrac1ipmodp$的取值,也就是$dispIaystyIefrac1i!times(i-1)!=frac1ipmodp$如果我們需要求$0!$到$n!$的逆元,對(duì)于每個(gè)元素都求一遍,就顯得有點(diǎn)慢。逆元可以看作是求倒數(shù)。那么不就有$displaystylefrac1(n+1)!times(n+1)=frac1n!pmodp$intinv(intb,intp)inta,k;exPower(b,p,a,k);if(a0)a+=p;returna;voidinit(intn)Fact0=1;for(inti=1
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 學(xué)校內(nèi)部控制體系建設(shè)與自查實(shí)踐深度解析
- 了解2025年證券從業(yè)資格證考試評(píng)分標(biāo)準(zhǔn)試題及答案
- DB36T-紅壤旱地周年油菜-花生-芝麻輪作技術(shù)規(guī)程編制說(shuō)明
- 2024年體育經(jīng)紀(jì)人考試概述
- 電力員工培訓(xùn)課件
- 方法論:游泳救生員考試的試題及答案
- 2024籃球裁判員道德規(guī)范試題及答案
- 體育經(jīng)紀(jì)人資格考試注意事項(xiàng) 試題及答案
- 農(nóng)業(yè)植保員實(shí)踐技能試題及答案
- 探索模具設(shè)計(jì)師資格認(rèn)證的新視野試題及答案
- 手術(shù)患者轉(zhuǎn)運(yùn)交接課件
- 鐵路基礎(chǔ)知識(shí)考試題庫(kù)單選題100道及答案
- 藝校對(duì)舞蹈學(xué)生受傷免責(zé)協(xié)議書(shū)
- 《結(jié)構(gòu)健康監(jiān)測(cè)系統(tǒng)運(yùn)行維護(hù)與管理標(biāo)準(zhǔn)》
- 江西版小學(xué)四年級(jí)下冊(cè)美術(shù)全冊(cè)教案
- 帕金森病的作業(yè)治療
- 外國(guó)教育史知到智慧樹(shù)章節(jié)測(cè)試課后答案2024年秋山東師范大學(xué)
- 手術(shù)室信息安全管理制度
- 社區(qū)創(chuàng)建消防安全示范社區(qū)方案樣本(4篇)
- 人教版-音樂(lè)-九年級(jí)下冊(cè)-《隱形的翅膀》教學(xué)課件
- 《沉積礦床》課件
評(píng)論
0/150
提交評(píng)論