目錄

題目(來(lái)源洛谷3811)

逆元定義

求逆元的幾種方法

一、拓展歐幾里得版

二、快速冪（分治思想）

遞歸快速冪

非遞歸快速冪

三、線(xiàn)性算法

“碎碎念”

---

題目(來(lái)源洛谷3811)

題目背景

這是一道模板題

題目描述

給定?n,p?求 1～n?中所有整數(shù)在模?p?意義下的乘法逆元。

輸入格式

一行兩個(gè)正整數(shù)?n,p。

輸出格式

輸出?n?行，第?i?行表示?i?在模?p?下的乘法逆元。

樣例

輸入

10 13

輸出

1 7 9 10 8 11 2 5 3 4

說(shuō)明

1 ?n??，n < p < 20000528

輸入保證?p?為質(zhì)數(shù)。

(((這題貌似只能用第三種線(xiàn)性的方法過(guò)哈，其它的會(huì)超時(shí)...

逆元定義

若 a ? x ≡ 1(mod b)，且a與b互質(zhì)，那么我們就能定義:?x?為?a?的逆元，記為，所以我們也可以稱(chēng)?x為?a?在?mod b?意義下的倒數(shù)，

所以對(duì)于 ??(mod p)?，我們就可以求出?b?在?mod p?下的逆元，然后乘上?a?，再?mod p，就是這個(gè)分?jǐn)?shù)的值了。

求逆元的幾種方法

一、拓展歐幾里得版

單個(gè)查找效率不錯(cuò)，比大部分方法要快（尤其對(duì)于mod p 比較大的時(shí)候）

好處就是，當(dāng)ap(互質(zhì))，但p不是質(zhì)數(shù)的時(shí)候也可以使用。

【不要問(wèn)我為什么不解釋，懂的人覺(jué)得“十分容易理解”，很不幸，我個(gè)fw不懂，先就背下來(lái)完事兒叭qwq】

#include<stdio.h> typedef long long ll; void Exgcd(ll a, ll b, ll &x, ll &y){ // &x 為"引用",可理解為//在其它函數(shù)內(nèi)也能改變main里的變量，沒(méi)有指針那么麻煩 if(!b) x = 1, y = 0;else Exgcd(b, a%b, y, x), y-=a/b*x; } int main(){ll x, y, n, p,a;scanf("%lld %lld",&n,&p);for(int i=1;i<=n;i++){a=i;Exgcd(a, p, x, y);x = (x%p+p)%p;printf("%lld\n",x); //x是a在mod p下的逆元} }

二、快速冪（分治思想）

快速冪（Exponentiation by squaring,平方求冪) 是一種簡(jiǎn)單而有效的小算法，它可以以O(shè)(log n)的時(shí)間復(fù)雜度計(jì)算乘方。

讓我們先來(lái)思考一個(gè)問(wèn)題：7的10次方，怎樣算比較快？

方法1：最樸素的想法，7*7=49，49*7=343，... 一步一步算，共進(jìn)行了9次乘法。

這樣算無(wú)疑太慢了，尤其對(duì)計(jì)算機(jī)的CPU而言，每次運(yùn)算只乘上一個(gè)個(gè)位數(shù)，無(wú)疑太屈才了。這時(shí)我們想到，也許可以拆分問(wèn)題。

方法2：先算7的5次方，即7*7*7*7*7，再算它的平方，共進(jìn)行了5次乘法。

但這并不是最優(yōu)解，因?yàn)閷?duì)于“7的5次方”，我們?nèi)匀豢梢圆鸱謫?wèn)題。

方法3：先算7*7得49，則7的5次方為49*49*7，再算它的平方，共進(jìn)行了4次乘法。

模仿這樣的過(guò)程，我們得到一個(gè)在?O(log n)?時(shí)間內(nèi)計(jì)算出冪的算法，也就是快速冪。

即二分思路，可得

遞歸快速冪

int qpow(int a, int n){if (n == 0) return 1;else if (n % 2 == 1)return qpow(a, n - 1) * a;else{int temp = qpow(a, n / 2); //注意這個(gè)temp變量是必要的return temp * temp; } }

注意上述代碼中temp變量是必要的，否則若寫(xiě)成qpow(a, n /2)*qpow(a, n /2)，那就會(huì)計(jì)算兩次,整個(gè)算法就退化為了O(n)?.

遞歸雖然簡(jiǎn)潔，但會(huì)產(chǎn)生額外的空間開(kāi)銷(xiāo)。我們可以把遞歸改寫(xiě)為循環(huán)，來(lái)避免對(duì)棧空間的大量占用，也就是

非遞歸快速冪

我們將指數(shù)轉(zhuǎn)換為二進(jìn)制的形式：??又發(fā)現(xiàn)（8=）即

?先只是冪 的代碼好理解：

//非遞歸快速冪 int qpow(int a, int n){int ans = 1;while(n){if(n&1) //如果n的當(dāng)前末位為1ans *= a; //ans乘上當(dāng)前的aa *= a; //a自乘n >>= 1; //n往右移一位}return ans; }

前期預(yù)備了下快速冪?的原理，接下來(lái)了解下此處要用到的費(fèi)馬小定理

若p為素?cái)?shù)，a為正整數(shù)，且a、p互質(zhì)。 則有?≡ 1(mod p)。式 子右邊恰好為1；

所以我們就可以放入原式，就可以得到：

a ? x ≡ 1(mod p)

a ? x ≡ (mod p)

x ≡ ?(mod p)

所以我們可以用快速冪來(lái)算出??(mod p)的值，這個(gè)數(shù)就是它的逆元了

【理解了之前的代碼，再看這個(gè)加上模除的代碼應(yīng)該就好理解了（順帶簡(jiǎn)化了下bushi】

#include<stdio.h> typedef long long ll; ll n, p; ll qpow(ll x ,ll pow, ll mod){ll ans = 1;for(; pow; pow>>=1, x = x * x % mod)if(pow & 1) ans = ans * x % mod;return ans; } int main(){scanf("%d %d",&n,&p);for(int i=1;i<=n;i++){ll x = qpow(i,p-2,p);printf("%lld\n",x);}return 0; }

三、線(xiàn)性算法

用于求一連串?dāng)?shù)字對(duì)于一個(gè)mod p的逆元。

只能用這種方法，別的算法都比這些要求一串要慢。

【核心代碼也就一行，窩理解不了，背叭QWQ】

#include<stdio.h> long long inv[3000006]; int main(){long long n,p;int i;scanf("%lld %lld",&n, &p); inv[1]=1;printf("1\n");for(i=2; i<=n; i++){inv[i]=(p-p/i)*inv[p%i]%p;printf("%lld\n",inv[i]);}return 0; }

“碎碎念”

就是說(shuō)，模糊的代碼要多看一看、查一查、敲一敲，（說(shuō)不定突然就理解了呢QWQ）比如窩這次看快速冪的方法，就由原來(lái)的一點(diǎn)不懂到差不多懂了(bushi)。特地整理一下,方便(有需要的uu們和)窩再看（我知道大佬們覺(jué)得賊簡(jiǎn)單，但我是真的是"一看就忘"型QWQ）

總結(jié)

以上是生活随笔為你收集整理的3811乘法逆元的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。