蓝桥杯题目：既约分数
思路分析：
首先我们需要利用双层循环搭配产生分子与分母，得到这些数字后，在循环中判断这两个数是否满足他们的最大公约数为1即可，那么我们先做框架，再做细节，所以主函数（框架）这样设计：
1. int main() 2. { 3. int i = 0; 4. int count = 0; 5. for (i = 1; i <= 2020; i++) 6. { 7. int j = 0; 8. for (j = 1; j <= 2020; j++) 9. { 10. if (gcd(i, j) == 1)//判断他们的最大公约数是否为1 11. count++; 12. } 13. } 14. printf("%d", count); 15. return 0; 16. }
之后我们只需要再做细节，设计函数，如果你不知道如何设计求最大公约数的函数的话，在文章后面详细讲解了如何求最大公约数以及如何求最小公倍数。
完整代码：
1. int gcd(int a, int b) 2. { 3. int z = b; 4. while (a % b) 5. { 6. z = a % b; 7. a = b; 8. b = z; 9. } 10. return z; 11. } 12. 13. int main() 14. { 15. int i = 0; 16. int count = 0; 17. for (i = 1; i <= 2020; i++) 18. { 19. int j = 0; 20. for (j = 1; j <= 2020; j++) 21. { 22. if (gcd(i, j) == 1) 23. count++; 24. } 25. } 26. printf("%d", count); 27. return 0; 28. }
答案：2481215
求最大公约数：
一、辗转相除法
通俗的将就是让两个数除留余数，当余数不为0时，继续用除数除以得到的余数，重复这一过程直到余数为0，此时的除数即为最大公约数，用图片表示为：
代码实现：
1. int gcd(int a, int b) 2. { 3. int z = b;//如果初始情况a%b的结果为0，那么此时除数b的值即为最大公约数 4. while(a % b!= 0) 5. { 6. z = a % b; 7. a = b; 8. b = z; 9. } 10. return z; 11. }
二、更相减损法
以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。循环这个操作，直到所得的减数和差相等为止。
代码实现：
1. int gcd(int a,int b) 2. { 3. while (a != b) 4. { 5. if (a > b) 6. { 7. a = a - b; 8. } 9. else 10. { 11. b = b - a; 12. } 13. return a; 14. } 15. }
三、穷举法
穷举法的思路很简单，他的最坏情况时间复杂度极高，不建议使用。
利用定义暴力穷举，创建一个临时变量保存其中一个数的值，循环判断是否满足最大公约数的定义，不满足就减一，直到找到这个数。
代码实现：
1. int gcd(int a, int b) 2. { 3. int tmp = 0; 4. for (tmp = a; ; tmp--) 5. { 6. if ((0 == a % tmp) && (0 == b % tmp)) 7. break; 8. } 9. return tmp; 10. }
四、递归（辗转相除）
思想同辗转相除法。
1. int gcd(int a, int b) 2. { 3. if (b == 0) 4. return a; 5. else 6. return gcd(b, a % b); 7. }
求最小公倍数：
一、穷举法
与求最大公约数的穷举法一样的思路，同样他最坏情况的时间复杂度非常高，不建议使用。
代码实现：
1. int lcm(int a, int b) 2. { 3. int tmp = a > b ? a : b; 4. while (1) 5. { 6. if ((0 == tmp % a) && (0 == tmp % b)) 7. break; 8. tmp++; 9. } 10. return tmp; 11. }
我们可以对这个穷举法进行一定的优化，由每次加一试数改为以乘数加一试数。
代码实现：
1. int lcm(int a, int b) 2. { 3. int i = 1; 4. while ((a * i) % b) 5. { 6. i++; 7. } 8. return (a * i); 9. }
二、a*b/最大公约数
此方法利用最小公倍数的定义得到，即最小公倍数= a*b/最大公约数。
1. int lcm(int a, int b) 2. { 3. int z = 0; 4. int n = a * b; 5. //计算最大公约数z 6. while (z = a % b) 7. { 8. a = b; 9. b = z; 10. } 11. return (n / z);//最小公倍数=（a*b）/最大公约数 12. }
求最大公约数类似的问题在算法比赛中很常见，希望这篇文章可以给你带来收获。
🔥🔥🔥
