2020年第十一届蓝桥杯 - 省赛 - C&C++大学A组 - B.既约分数

Ideas

这题就是简单的暴力枚举，把分子和分母都从1枚举到2020，然后判断分子和分母的的最大公约数是不是1就OK了。

计算最大公约数的函数gcd直接默写。

Code Python

def gcd(a, b): return a if b == 0 else gcd(b, a % b) if __name__ == '__main__': ans = 0 for zi in range(1, 2021): for mu in range(1, 2021): if gcd(zi, mu) == 1: ans += 1 print(ans) 

C++

#include   using namespace std; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int main() { int ans = 0; for (int i = 1; i < 2021; i++) { for (int j = 1; j < 2021; j++) { if (gcd(i, j) == 1) { ans += 1; } } } cout << "ans = " << ans << endl; return 0; } 

Answer：2481215