1.4 既约分数(★)
题目信息
2020 年省赛-填空题
● C/C++ A组第2题；C/C++ B组第2题
● Java A组第2题
【问题描述】
如果一个分数的分子和分母的最大公约数是 
，这个分数称为既约分数。
例如 
， 都是既约分数。
请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1 和 2020 ）？
【答案提交】
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果作为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
题目分析
核心考点
● gcd（最大公约数）
用一句话概括题意，即统计分子、分母的范围均为 1 
2020 且分子、分母的最大公约数（gcd）为 1 的分数的个数。
解题的思路较为简单，只需从 1 2020 枚举分子，再从 1 2020 枚举分母，然后判断分子、分母的最大公约数是否为 1（若为 1 则答案个数+1）即可。不过在此之前，我们需要知道如何求解两个数的最大公约数。
求最大公约数的方法很多，如果想图个方便，可以直接调用 C++的 algorithm 库中的 ＿gcd() 函数来求解。如果不知道这个函数也没有关系，因为想求解两个数的最大公约数并不难。我们可以采用常用的辗转相除法（国际上也称"欧几里得算法"），它的代码如下。
参考代码1-4-1 【复杂度为 
】
1 int gcd(int a , int b){
2 if(b == 0) return a;
3 return gcd(b, a % b);
4 }知道了如何求解两个数的最大公约数后，就可以枚举统计答案了。
参考代码1-4-2 【复杂度为 
】
1 #include<bits/stdc++.h>
2 using namespace std;
3 signed main()
4 {
5 int ans = 0;
6 for(int i = 1 ; i <= 2020 ; i ++){
7 for(int j = 1 ; j <= 2020 ; j ++){
8 if(＿gcd(i , j) == 1) ans ++ ;
9 }
10 }
11 cout << ans << '\n';
12 return 0;
13 }最终答案为2481215。
拓展提高
我们来考虑一下如何优化程序的时间复杂度。
若两个数 
（ 
）的最大公约数为 1，则 
是一个既约分数， 
也是一个既约分数。所以我们可以从 
枚举 
，从 
枚举 
，这样得到的 就满足 
。接着判断 的最大公约数是否为 1（若为 1，则 是既约分数）。
若用 cnt 来统计有多少对 满足 且 的最大公约数为 1，则答案为 
（乘2是因为 的倒数 也是既约分数，减 1 是因为 
的倒数还是 ，重复计算了一次，要减掉，见下图）。
这样就可以细微地优化程序计算的次数了。
不过程序的复杂度仍为 
。有没有什么办法能降低复杂度呢?答案自然是有。
核心考点
● 唯一分解定理
● 欧拉函数
● 欧拉筛
对于最大公约数为 1 的两个整数，我们称它们的关系为互质。在数论中， 
中与 
互质的数的个数被称为欧拉函数（记作 
）。
由欧拉函数的定义可知满足 ，且 最大公约数为 的 的个数就为 
。
我们要求的是 内满足 且 
最大公约数为 1 的 的个数，即 内所有数的欧拉函数的和，即 
。
欧拉函数的通项公式：
其中 
为 的所有不重复质因子。
要想得到 的所有不重复质因子，我们可以采用数论利器——唯一分解定理。
提示
唯一分解定理就是对于一个大于 的整数 ，要么其本身是个质数，要么能被分解为有限个质数的乘积。
若用数学公式表示，则 
， 
表示质数（即 的质因子）， 
表示 的个数。
例如， 
就可以表示为 
，它的质因子有 
、 
。其中质因子 的个数为 ，质因子 的个数为 。
综上，我们可以写出如下代码，完成对 的不重复质因子的求解。
参考代码1-4-3
1 int p[N]; // p[] 记录因子，p[1]是最小因子
2 int getPrime(int n){
3 int k = 0; // k 记录 n 的质因子的个数
4 for(int i = 2 ; i * i <= n ; i ++){
5 if(n % i == 0) {
6 p[++ k] = i;
7 while(n % i == 0) n /= i; // 把 n 重复的质因子去掉
8 }
9 }
10 if(n > 1) p[++ k] = n; // n 没有被除尽，是素数
11 return n;
12 }再根据欧拉函数的通项公式 
写出代码。
参考代码1-4-4
1 int getPhi(int n){
2 int phi = n , k = getPrime(n);
3 for(int i = 1 ; i <= k ; i ++){ // 枚举所有质因子：p1,p2,...,pk
4 phi = phi - phi / p[i]; // (phi - phi / p[i])等价于 phi(1 - 1 / p[i])
5 }
6 return phi;
7 }因为在本题中质因子的作用只是为了计算欧拉函数，所以可以不用开辟数组记录质因子，而是每得到一个质因子就将其放入欧拉函数的通项公式中计算，这样两份代码就能合并在一起，具体代码可见参考代码1-4-5的第 
行。
参考代码1-4-5 【时间复杂度为 
】
1 #include<bits/stdc++.h>
2 using namespace std;
3 int solve(int n){
4 int phi = n;
5 for(int i = 2 ; i * i <= n ; i ++){
6 if(n % i == 0) { // i 是 n 的质因子
7 phi = phi - phi / i; // 将其丢入欧拉函数的通项公式中计算
8 while(n % i == 0) n /= i; // 把 n 重复的质因子去掉
9 }
10 }
11 if(n > 1) phi = phi - phi / n; // n 没有被除尽，是素数，将其丢入欧拉函数的通项公式中计算
12 return phi;
13 }
14 signed main()
15 {
16 int ans = 0;
17 for(int i = 1 ; i <= 2020 ; i ++) ans += solve(i);
18 cout << ans * 2 - 1 << '\n';
19 return 0;
20 }当然，求一个数的欧拉函数还有更好的求法，比如用Pollard_Rho 寻找因子、用Miller_Rabin 测试质数，以将复杂度优化到 
。不过这种做法码量极大，所涉及的知识点难度也高，蓝桥杯赛场上几乎是不可能用上的。
此外，我们还可以使用欧拉筛，它的作用是以 
的时间复杂度求出 
中每个数的欧拉函数。这样，程序的复杂度就可以被进一步优化。
参考代码1-4-6 【时间复杂度为 
】
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n , phi[2021] , prime[2021];
4 signed main(){
5 // 欧拉筛
6 phi[1] = 1;
7 for(int i = 2 ; i <= 2020 ; i ++){
8 if(!prime[i]) prime[++ n] = i, phi[i] = i - 1;
9 for(int j = 1 ; j <= n && i * prime[j] <= 2020 ; j ++){
10 prime[prime[j] * i] = 1;
11 if(i % prime[j] == 0){
12 phi[i * prime[j]] = phi[i] * prime[j];
13 break ;
14 }
15 phi[i * prime[j]] = phi[i] * (prime[j] - 1);
16 }
17 }
18 int cnt = 0;
19 for(int i = 1 ; i <= 2020 ; i ++) cnt += phi[i];
20 cout << 2 * cnt - 1 << '\n';
21 return 0;
22 }