既约分数 -- 辗转相除法

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

如果一个分数的分子和分母的最大公约数是 11，这个分数称为既约分数。

例如  , ,， 都是既约分数。

请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1 和 2020）？

运行限制

• 最大运行时间：2s
• 最大运行内存: 128M

题目来源：既约分数

1、题目分析

辗转相除法：求解两个整数的最大公约数

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：

1997 ÷ 615 = 3 (余 152)

615 ÷ 152 = 4(余7)

152 ÷ 7 = 21(余5)

7 ÷ 5 = 1 (余2)

5 ÷ 2 = 2 (余1)

2 ÷ 1 = 2 (余0)

至此，最大公约数为1

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。

//
b
a%b
int gcd(int a,int b){
return b == 0?b:gcd(b,a%b);
}

2、代码实现

public class _既约分数 {
static int gcd(int a,int b) {
return b == 0?a:gcd(b, a%b);
}
public static void main(String[] args) {
long res = 1L;
for(int i=1;i<2021;i++) {
for(int j=1;j<i;j++) {
if(gcd(i, j)==1) {
res+=2;
}
}
}
System.out.println(res);
}
}

最后

以上就是无奈钢笔为你收集整理的既约分数 -- 辗转相除法的全部内容，希望文章能够帮你解决既约分数 -- 辗转相除法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。