一、题目背景

本题为2020年省赛填空题

• C/C++ A 组第2题
• C/C++ B 组第2题
• Java A 组第2题

二、题目描述

如果一个分数的分子和分母的最大公约数是1，这个分数称为既约分数。
例如，$\frac{3}{4}$，$\frac{1}{8}$ ，$\frac{7}{1}$ 都是既约分数。
请问，有多少个既约分数，分子和分母都是1到2020之间的整数 ？
注意： 包括1和2020

三、题目分析

最大公约数：指两个或多个整数共有约数中最大的一个。
这道题求解1~2020中所有的既约分数，本质上就是求在1~2020这个范围内，所有分子和分母的最大公约数为1的分数个数。

1.求最大公约数

①辗转相减法

int gcd(int a,int b)
{        
    while(a != b)
    {
        if(a>b)
        {
            a = a - b;
        }
        else 
        {
            b = b - a;
        }
    }
    return a;
}

②穷举法

int gcd(int x,int y)
{
       int temp = 0;
    for(temp = x ; ; temp-- )
    {
        if(x%temp == 0 && y%temp==0) 
               break; 
       }
    return temp;
}

③辗转相除法

int gcd(int x,int y){
    int rem;
    while(n > 0){
        rem = x % y;
        x = y;
        y = rem;
    }
    return x;            
}

④辗转相除法（递归）

int gcd(int x, int y) {
    if (x%y==0)
        return y;
    else 
    return gcd(y, x%y);
    }

2.枚举求解

知道了如何判断最大公约数，剩下的循环枚举就很简单了。

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

四、代码汇总

1.C语言代码

#include<stdio.h>
int gcd(int x, int y) {
    if (x % y == 0)
        return y;
    else
        return gcd(y, x % y);
}
int main()
{
    int count = 0;
    for (int i = 1; i <= 2020; i++)
    {
        for (int j = 1; j <= 2020; j++)
        {
            if (gcd(i, j) == 1)
                count++;
        }
    }
    printf("%d", count);
    return 0;
}

2.C++代码

注意：C++的algorithm库中自带求最大公约数的函数（__gcd()）我们无需像C语言一样手写。

#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
    int count = 0;
    for (int i = 1; i <= 2020; i++)
    {
        for (int j = 1; j <= 2020; j++)
        {
            if (__gcd(i, j) == 1)
                count++;
        }
    }
    cout << count << endl;
}

3.运行结果

故最终答案为：2481215

五、总结

最大公约数的求法

最大公约数的求法有很多，我这里最推荐记忆递归版本的。
因为代码量少不容易写错。

int gcd(int x, int y) {
    if (x%y==0)
        return y;
    else 
    return gcd(y, x%y);
    }