一、题目

如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。
请问，有多少个既约分数，分子和分母都是 1到 2020 之间的整数（包括 1 和 2020）？

二、解题思路

这道题比较简单，而且是填空，直接用暴力算法双重循环。但是这个题用的最大公约数，我老是记不清辗转相除法，所以选这个题来写

三、辗转相除法

证明：

设两个数a，b（默认a>b）。因为等式，则a一定可以表示为a=xb+r，所以r=a-xb.

因为a和b有一个最大公因子d，所以等式右边可以整除d，那么等式左边一定也可以整除d。这样a,b,r都有一个共同的最大公因子，即gcd(a,b)=gcd(b,r)。也就是说我们可以把求两个数的最大公因数的问题转换成求两个数中较小的那个数和两个数相除得到的余数的最大公约数。

       另一方面，我们知道一个数和0的最大公因子就是这个数本身（虽然这么说感觉没什么意义的样子），所以我们只要一直递归使上一次的除数作为下一次的被除数，上一次的余数作为除数，直到余数为零的时候，这个除数就是最大公因数。

     同时证明一下欧几里得算法必然在有限步内结束，我们可以看到，一个大数除以一个小数，如果没有余数，那最大公约数就是那个小数，如果有余数，那余数必然比除数和被除数小，我们拿其中除数b和余数r再做一次除法，得到的余数一定更小，假设一直有余数，那余数最小是1，此时任何一个除数除以1都是0，所以所有的数一定至少有一个最大公约数是1，因为余数必有一个时刻是1，这时候再对除数和1进行一次gcd，余数肯定是0。然后就是通过上面得到的结论，判断出此时余数为0时刻的式子中除数1即为最大公约数。

      所以我们可以用递归算法。判断余数是否为零，如果不为零则对除数和余数再做一次gcd，直到余数为0。具体函数如下：

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;
}

五、参考资料

百度百科：欧几里得算法

知乎：欧几里得算法：计算两个正整数的最大公约 数 https://zhuanlan.zhihu.com/p/51411526