? use C++11
? tip: 函數(shù)內(nèi)必須是用變量來(lái)傳輸引用形參

創(chuàng)新互聯(lián)專注于福建網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供福建營(yíng)銷型網(wǎng)站建設(shè)，福建網(wǎng)站制作、福建網(wǎng)頁(yè)設(shè)計(jì)、福建網(wǎng)站官網(wǎng)定制、小程序制作服務(wù)，打造福建網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供福建網(wǎng)站排名全網(wǎng)營(yíng)銷落地服務(wù)。

倍數(shù)

1. 若 \(a,b,k \in \mathbb N\)，且 \(a \times k=b\)，那么 \(b\) 是 \(a\) 的倍數(shù)，稱 \(a\) 整除 \(b\)，記作 \(a \mid b\)。

2. \([1,n]\in \mathbb N\) 中 \(x \in \mathbb N\) 的倍數(shù)有 \(\left \lfloor \dfrac{n}{x} \right \rfloor\) 個(gè)。

約數(shù)

1. 若 \(a \mid b\)，\(a,b\in\mathbb N\)，那么 \(a\) 是 \(b\) 的約數(shù)。

2. \(a \in \mathbb N\) 的約數(shù)個(gè)數(shù)是有限的，記作 \(\operatorname d(n)\)，\(\in \mathbb Z\)。

3. 快速算一個(gè)序列的 \(\operatorname d(n)\)：設(shè)一個(gè)計(jì)數(shù)數(shù)組對(duì)應(yīng)每個(gè)數(shù)，初始為 0，從左到右計(jì)算每個(gè)數(shù)，對(duì)于每個(gè)倍數(shù)加 1，當(dāng)整個(gè)序列計(jì)算完后，計(jì)數(shù)數(shù)組的值是其對(duì)應(yīng)數(shù)字的約數(shù)個(gè)數(shù)，時(shí)間復(fù)雜度 \(\mathcal{O}(n\log n)\) 下面是一個(gè)例子以及代碼實(shí)現(xiàn)。

n    1  2  3  4  5  6
d(n) 0  0  0  0  0  0  start
    +1 +1 +1 +1 +1 +1  step 1 in number 1
     0 +1  0 +1  0 +1  step 2 in number 2
     0  0 +1  0  0 +1  step 3 in number 3
     .....and more
     1  2  2  3  2  4  end

void approximate_number(long long *num,long long &to){
	for(long long i=1;i<=to;++i)
		for(long long j=i;j<=to;j+=i)
			(*(num+j))++;
}

素?cái)?shù)

1. 1 不是素?cái)?shù)也不是合數(shù)。

2. 下面是一串判斷 \(n\in \mathbb N\) 是否是素?cái)?shù)的代碼，時(shí)間復(fù)雜度 \(\mathcal{O}(\sqrt n)\)。

bool is_prime(long long &n){
	if(n==1)	return false;
	for(long long i=2;i<=n/i;++i)
		if(n%i==0)	return false;
	return true;
}

3. 計(jì)算一個(gè)序列每個(gè)數(shù)是否是素?cái)?shù)：樸素篩法，有較多重復(fù)判斷，時(shí)間復(fù)雜度 \(\mathcal{O}(n\log n)\)；埃式篩法，僅是素?cái)?shù)才向后篩，優(yōu)化樸素篩法，時(shí)間復(fù)雜度 \(\mathcal{O}(n\log\log n)\)，接近線性篩。

最大公約數(shù)

1. 若 \(a,b\in \mathbb N\) 且 \(k \mid a,b \in \mathbb N\)，且不存在更大的 \(k\)，稱 \(k\) 是 \(a,b\) 的最大公約數(shù)。

2. 快速求 \(a,b\in \mathbb N\) 的最大公約數(shù)，歐幾里得定理：\(\gcd(a,b)=\gcd(b,a \bmod b)\)。

3. 已知 \(a,b \in \mathbb N\)，可找到 \(x,y \in \mathbb Z\) 使 \(a\times x +b\times y=\gcd(a,b)\)，若 \(a\times x+b\times y=1\) 有解，則 \(a\) 和 \(b\) 互質(zhì)。

4. 擴(kuò)展歐幾里得，一定存在 \(x,y\in \mathbb N\) 使貝祖等式 \(a\times x +b\times y=\gcd(a,b)\)\(\Rightarrow (\left \lfloor a \div b \right \rfloor \times b + a \bmod b) \times x + b\times y = \gcd(b,a\bmod b)\)\(\Rightarrow (\left \lfloor a \div b \right \rfloor \times x + y)\times b +(a \bmod b)\times x\)，可得新的方程 \(b \times x'+(a \bmod b)\times y' = \gcd(b,a\bmod b)\) 因此可得 \(\begin{cases}x'=(\left \lfloor a \div b \right \rfloor\times x+y)\\y'=x\end{cases}\)，同樣倒推可得特解 \(\begin{cases}x=y'\\y=x'-(\left \lfloor a \div b \right \rfloor\times y')\end{cases}\)，下面是遞歸代碼實(shí)現(xiàn)。

#include<array>
array<long long,3> exgcd(long long &a,long long &b){
	if(b==0)	return {1,0,a};
	//當(dāng)b=0時(shí)，等式為ax=gcd(a,0)，即ax=a
	//得x=1,y=0
	array<long long,3> ans=exgcd(b,a%b);
	long long temp=ans[0];
	ans[0]=ans[1];
	ans[1]=temp-a/b*ans[1];
	return ans;//ans[0]為x，ans[1]為y，ans[2]為gcd(a,b)
}

5. 當(dāng)求得貝祖等式特解 \(x_0,y_0\in \mathbb N\) 后，可得 \(x,y\in \mathbb N\) 通解，設(shè) \(g=\gcd(a,b)\) 通解為 \(\begin{cases}x=x_0+t\times b\div g\\y = y_0- t \times a \div g\end{cases}\)，推導(dǎo)過(guò)程：\(\begin{cases}a\times x+b\times y=g\\a\times x_0+b\times x_0=g\end{cases}\)\(\Rightarrow (x-x_0)\times a+(y-y_0)\times b=0\)\(\Rightarrow (x-x_0)\times a=(y_0-y)\times b\)\(\Rightarrow (x-x_0)\times \dfrac{a}{g}=(y_0-y)\times \dfrac{g}\)\(\Rightarrow \begin{cases}x-x_0=t\times \dfrac{g}\\y_0-y=t \times \dfrac{a}{g}\end{cases}\)\(\Rightarrow \begin{cases} x=x_0+t\times\dfrac{g}\\y=y_0-t\times\dfrac{a}{g}\end{cases}\)，其中 \(x\) 的第一個(gè)解是 \(\bigg(x\bmod\dfrac{g}+\dfrac{g}\bigg)\bmod \dfrac{g}\)。

模運(yùn)算

1. 已知 \(a,b,p\in \mathbb N\)，\((a+b)\bmod p=(a\bmod p+b\bmod p)\bmod p\)，\((a-b)\bmod p=(a\bmod p+b\bmod p)\bmod p\)，\((a\times b)\bmod p=(a \bmod p\times b\bmod p)\bmod p\)。

2. 若需要進(jìn)行除法的模運(yùn)算，與普通的不同，例子：\(\dfrac{20}{10}\bmod 5 \neq \dfrac{20 \bmod 5}{10\bmod 5}\bmod 5\)，所以為了求 \((a\div b) \bmod p\)，\(a,b,p\in\mathbb N\)，需要找到 \(b\) 的乘法逆元 \(x\in\mathbb N\)，將算式變成 \((a\times x)\bmod p\)。

3. 已知 \(a,x,m\in \mathbb N\)，\(ax \equiv 1\pmod p\)\(\Rightarrow ax \bmod p=1\)\(\Rightarrow ax-\left\lfloor\dfrac{ax}{p}\right\rfloor\times p=1\)，稱 \(x\) 是關(guān)于 \(a\) 的乘法逆元，將 \(-\left\lfloor\dfrac{ax}{p}\right\rfloor\) 用 \(y\) 替代，得 \(ax+py=1\)，即找到 \(x\) 的值即可找到 \(a\) 的乘法逆元，也可知 \(a,p\) 必須要互質(zhì)。

冪

1. 求 \(a^b\)，\(a,b\in \mathbb N\)，暴力：重復(fù)乘 \(b\) 次 \(a\)，時(shí)間復(fù)雜度 \(\mathcal{O}(b)\)，可以優(yōu)化。

2. 快速冪，時(shí)間復(fù)雜度 \(\mathcal{O}(\log b)\)，采用分治思想，對(duì)于一個(gè) \(a^b\)，\(a,b\in \mathbb {N^*}\)，若 \(b\) 為復(fù)數(shù)，可推 \(a^b=a^{2^{b\div 2}}\)，若 \(b\) 為奇數(shù)，分出一個(gè) \(a\)，可推 \(a^b=a^{2^{(b-1)\div 2}}\times a\)，例子： \(a\leftarrow 5,b\leftarrow 6\)，\(a^b=5^6=5^{2^3}=25^3=25^2\times 25=125\times 25\)，易發(fā)現(xiàn) \(a^b\) 就是求分治過(guò)程中被分出來(lái)的 \(a\) 的積，以下是代碼實(shí)現(xiàn)。

long long quick_pow(long long a,long long b){
	long long ans=1;
	while(b>0){
		if(b&1)	ans*=a;
		a*=a;
		b>>=1;
	}
	return ans;
}

網(wǎng)站欄目：數(shù)論入門、歐幾里得及其擴(kuò)展
分享網(wǎng)址：http://chinadenli.net/article44/dsoiiee.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動(dòng)網(wǎng)站建設(shè)、App開發(fā)、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站維護(hù)、靜態(tài)網(wǎng)站、網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)