当前位置：网站首页>蓝桥历届真题-既约分数

蓝桥历届真题-既约分数

2022-08-09 13:04:00 【CoolTiger_程序员】

在这里插入图片描述
答案:

2481215

思路：
遍历1-2020之间的任意点对，判断gcd是否为1，计数。
使用欧几里得算法（辗转相除法）

#include<stdio.h>
int gcd(int a,int b){
    
	if(b==0) return a;
	return gcd(b,a%b);
}

int main(){
    
	int i,j;
	int count=0;
	for(i=1;i<=2020;i++){
    
		
		for(j=1;j<=2020;j++){
    
			if(gcd(i,j)==1)
			count++;
		}
	}
	printf("%d\n",count);
	return 0;
}

2481215

--------------------------------
Process exited after 0.4831 seconds with return value 0
请按任意键继续. . .
原网站

版权声明
本文为[CoolTiger_程序员]所创，转载请带上原文链接，感谢
https://blog.csdn.net/mjh1667002013/article/details/115431255

边栏推荐

猜你喜欢

随机推荐