每日一练蓝桥杯C/C++B组~既约分数
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。
例如 3/4 ,1/8 ,7/1,都是既约分数。
请问，有多少个既约分数，分子和分母都是 1 到 2020之间的整数（包括 1和 2020）？
答案：2481215
#include<iostream> using namespace std; int gcd(int a,int b){ //辗转相除法求最大公约数 return b == 0 ? a:gcd(b,a%b); } int main(){ int ans = 0; for(int zi = 1;zi <= 2020;zi++){ for(int mu = 1;mu <= 2020;mu++){ if(gcd(zi,mu) == 1){ ans++; } } } cout << "ans = " << ans << endl; return 0; }
代码思路：
既约分数声明ans初始化0，分子分母for循环，gcd(zi,mu)求最大公约数为1，既约分数加1。
int main(){ int ans = 0; for(int zi = 1;zi <= 2020;zi++){ for(int mu = 1;mu <= 2020;mu++){ if(gcd(zi,mu) == 1){ ans++; } } } cout << "ans = " << ans << endl; return 0; }
辗转相除法，如果b为0，则返回a,否则返回gcd，那么b等于0，相当a对b取余等于0，a返回上一回b值。你可以把它当成一个公式背下来.
int gcd(int a,int b){ //辗转相除法求最大公约数 return b == 0 ? a:gcd(b,a%b); }
