signed

QiShunwang

“诚信为本、客户至上”

2020年蓝桥杯Java A组 B题 既约分数

2021/3/21 10:37:42   来源:

题目

**[描述]**如果一个分数的分子和分母的最大公约数是1,这个分数称为既约分数。例如,3/4 , 5/2 , 1/8 , 7/1都是既约分数。请问,有多少个既约分数,分子和分母都是1 到2020 之间的整数(包括1和2020)?

相关数论知识

参考:如何判断两个数之间是否互质?
用代码实现有以下两种方法:
1. 求差判断法
如果两个数相差不大,可先求出它们的差,再看差与其中较小数是否互质。如果互质,则原来两个数一定是互质数。
2. 求商判断法
用大数除以小数,如果除得的余数与其中较小数互质,则原来两个数是互质数。

但是,在实现代码的过程中,以上两种方法只能笔算,并不能实际写代码。所以,我们需要经典的欧几里得算法——辗转相除法
思想是:两个数字同时除以他们中比较小的那个,如果除出来没有余数,那你就找到最大公约数(也就是最小的那个数字)
Ps:互质,即要求判断两者最大公约数是否为1,如果为1的话两个数之间互质。

实现

public class Main {
    //这个函数就是求最大公约数
	public static int gcd(int a, int b) {;
		if (b == 0) 
			return a;
		//如果一开始a小于b,那么下一个次的迭代就是互换顺序,往后的a都大于b
		return gcd(b, a % b);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int count = 0;
		for(int i = 1; i <= 2020; i++) {
			for(int j = 1; j <= 2020; j++) {
				if(gcd(i, j) == 1) {
					count++;
				}
			}
		}
		System.out.println(count);
	}
}

结果

2481215

期待你的三连,冲鸭