蓝桥杯2020年省赛C/C++B组第2题 既约分数

解题思路：本题关键是掌握求最大公约数的方法——辗转相除法，其次就是注意如何减少遍历次数，我们不需要进行完全枚举，因为既然是既约分数，它本身的分子和分母倒过来组成的新的数也是既约分数，我们只需要统计一边即可，将统计完的的结果×2-1便是最终结果(因为1/1倒过来一样，所以要减去这一重复统计的结果)

#include<stdio.h> 
int gcd(int a,int b)//创建一个求最大公约数的函数
{
 if(b==0) return a;//如果余数为零，则返回除数即最大公约数
 else return gcd(b,a%b);//如果余数不为零，就继续递归求最大公约数
}
int main()
{
 long long int ans=0;
 for(int i=1;i<=2020;i++)
 {
  for(int j=1;j<=i;j++)//让j<=i即可，减少遍历次数
  {
   if(gcd(j,i)==1) ans++;//如果最大公约数为1就统计一次
  }
 }
 long long int cnt=ans*2-1;//j/i为既约分数，那么它的倒数i/j也为既约分数，但要把1/1这种重复情况
 printf("%lld\n",cnt);//输出最终结果                                                //减掉
 return 0;  
}