本次內(nèi)容包括：快速冪，拓展歐幾里得，同余逆元，埃氏篩法

快速冪

背景：求a的n次冪
常規(guī)方法：循環(huán)累乘 復(fù)雜度O(n）
數(shù)論方法：快速冪，使用二進(jìn)制拆分或分治。復(fù)雜度對數(shù)級

二進(jìn)制拆分：將n從二進(jìn)制角度去看，不斷二進(jìn)制右移，當(dāng)末位為1則乘，每次右移都會改變乘數(shù)1 2 4 8。
代碼：

int fastpow(int a,int n) {int base=a;int ans=1;while(n){if(n&1){ans*=base;}base*=base;n>>=1;} }

或者有

int fastpow(int a,int n) {int ans=1;while(n){if(n&1){ans*=a;}a=fastpow(a,a)n>>=1;} }

分治：層層拆分后分堆合并。
代碼:

int fastpow(int a,int n) {int temp;if(n==1)return a;temp=fastpow(a,n/2);if(n&1)return temp*temp*a;return temp*temp; }

temp=fastpow(a,n/2);注意這一步

拓展：矩陣快速冪
重點：將矩陣視為同快速冪中的整數(shù)元素即可。
主要操作有：定義矩陣乘法，初始化矩陣，設(shè)置單位矩陣。
0.
初始化矩陣

struct matrix {int m[50][50];matrix(){memset(m,0,sizeof(m));} };

1.矩陣乘法線性代數(shù)有學(xué)不再說明：

Matrix multi(matrix a,matrix b)//乘法二元操作 {matrix res;for(int i=0;i<50;i++){for(int j=0;j<50;j++){for(int k=0;k<50;k++){res.m[i][j]+=a.m[i][k]*b.m[k][j];//從左向右，分行乘列，層層進(jìn)行}}}return res; }

2.設(shè)置單位矩陣與矩陣快速冪

int fastpow(matrix a,int n) {matrix res;for(int i=0;i<50;i++)res.m[i][i]=1;while(n){if(n&1)Matrixmulti(res,a);a=Matrixmulti(a,a);n>>=1;}return res; }

拓展歐幾里得

四步走，我之前有寫，不再寫了。

同余逆元

同余: a和b取模于m的余數(shù)相同，成為同余。
性質(zhì)：a-b是m的整數(shù)倍
應(yīng)用：構(gòu)成二元一次方程ax+by=mn
逆元: ax和1取模于m同余。得到ax-my=1，得到ax+my=1視m為參數(shù)，加號可允許m可正可負(fù)，得到二元一次方程之后，用拓展歐幾里得求解的得出逆元
代碼：

int inverse(int a,int b) {int x,int y;exgcd(a,m,x,y);return (m+x%m)%m;//a模m的逆 }

應(yīng)用：逆元與除法取模
a，b，k設(shè)k是b的逆元
則對于（a/b）%m=ak%m

求二元一次方程
如果知道了a的逆，那么可求ax與b取模m同余的方程，
設(shè)a的逆為k
x與k*b取模于m同余。

埃氏篩法

思想：找從2到n所有的素數(shù)，從頭開始，2是最小的素數(shù)，然后把2-n中所有2的倍數(shù)刪去，下一個素數(shù)是3，把所有3的倍數(shù)刪去。
實操：刪除操作可以用單鏈表，也可以用標(biāo)記數(shù)組來完成。

總結(jié)

以上是生活随笔為你收集整理的简单数论学的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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