一、題目

如果一個(gè)分?jǐn)?shù)的分子和分母的最大公約數(shù)是 1，這個(gè)分?jǐn)?shù)稱為既約分?jǐn)?shù)。
請問，有多少個(gè)既約分?jǐn)?shù)，分子和分母都是 1到 2020 之間的整數(shù)（包括 1 和 2020）？

二、解題思路

這道題比較簡單，而且是填空，直接用暴力算法雙重循環(huán)。但是這個(gè)題用的最大公約數(shù)，我老是記不清輾轉(zhuǎn)相除法，所以選這個(gè)題來寫

三、輾轉(zhuǎn)相除法

證明：

設(shè)兩個(gè)數(shù)a，b（默認(rèn)a>b）。因?yàn)榈仁?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=a%5Cdiv%20b%3Dx%C2%B7%C2%B7%C2%B7%C2%B7%C2%B7%C2%B7r" alt="a%5Cdiv%20b%3Dx%C2%B7%C2%B7%C2%B7%C2%B7%C2%B7%C2%B7r"/>，則a一定可以表示為a=xb+r，所以r=a-xb.

因?yàn)閍和b有一個(gè)最大公因子d，所以等式右邊可以整除d，那么等式左邊一定也可以整除d。這樣a,b,r都有一個(gè)共同的最大公因子，即gcd(a,b)=gcd(b,r)。也就是說我們可以把求兩個(gè)數(shù)的最大公因數(shù)的問題轉(zhuǎn)換成求兩個(gè)數(shù)中較小的那個(gè)數(shù)和兩個(gè)數(shù)相除得到的余數(shù)的最大公約數(shù)。

? ? ? ?另一方面，我們知道一個(gè)數(shù)和0的最大公因子就是這個(gè)數(shù)本身（雖然這么說感覺沒什么意義的樣子），所以我們只要一直遞歸使上一次的除數(shù)作為下一次的被除數(shù)，上一次的余數(shù)作為除數(shù)，直到余數(shù)為零的時(shí)候，這個(gè)除數(shù)就是最大公因數(shù)。

? ? ?同時(shí)證明一下歐幾里得算法必然在有限步內(nèi)結(jié)束，我們可以看到，一個(gè)大數(shù)除以一個(gè)小數(shù)，如果沒有余數(shù)，那最大公約數(shù)就是那個(gè)小數(shù)，如果有余數(shù)，那余數(shù)必然比除數(shù)和被除數(shù)小，我們拿其中除數(shù)b和余數(shù)r再做一次除法，得到的余數(shù)一定更小，假設(shè)一直有余數(shù)，那余數(shù)最小是1，此時(shí)任何一個(gè)除數(shù)除以1都是0，所以所有的數(shù)一定至少有一個(gè)最大公約數(shù)是1，因?yàn)橛鄶?shù)必有一個(gè)時(shí)刻是1，這時(shí)候再對除數(shù)和1進(jìn)行一次gcd，余數(shù)肯定是0。然后就是通過上面得到的結(jié)論，判斷出此時(shí)余數(shù)為0時(shí)刻的式子中除數(shù)1即為最大公約數(shù)。

? ? ? 所以我們可以用遞歸算法。判斷余數(shù)是否為零，如果不為零則對除數(shù)和余數(shù)再做一次gcd，直到余數(shù)為0。具體函數(shù)如下：

int gcd(int x,int y)
{
	return x%y? gcd(y,x%y):y; 
}

四、完整代碼

#include <bits/stdc++.h>
using namespace std;
int a,b;
long long ans=0;
int gcd(int x,int y)
{
	return x%y? gcd(y,x%y):y; 
}
int main()
{
	for(int i=1;i<=2020;i++){
		for(int j=1;j<=2020;j++){
			if(i<j) {a=j;b=i;}
			else {a=i;b=j;}
			if(gcd(a,b)==1) ans++;
		}
	}
	cout<<ans;
	return 0;
}

五、參考資料

百度百科：歐幾里得算法

知乎：歐幾里得算法：計(jì)算兩個(gè)正整數(shù)的最大公約 數(shù) https://zhuanlan.zhihu.com/p/51411526