【洛谷题解】P1029[普及组]最大公约数和最小公倍数问题

本文主要是介绍【洛谷题解】P1029[普及组]最大公约数和最小公倍数问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：[NOIP2001 普及组] 最大公约数和最小公倍数问题 - 洛谷

题目难度：普及-

涉及知识点：stl函数，最大公因数，最小公倍数

题意：

输入输出样例：

分析：直接套用公式优化累加即可

AC代码：

#include<bits/stdc++.h>//可使用STL函数：__gcd判断最大公因数
using namespace std;
int main()
{int a,b,ans=0;ios::sync_with_stdio(false);//加快cin，coutcin>>a>>b;for(int i=a;i<=b;i++){//再来一个for循环会超时int j=a*b/i;//最大公因数==（a*b）/__gcd(a,b),所以一因数==最大公因数*最小公倍数/另一因数if(__gcd(i,j)==a&&(i*j)/__gcd(i,j)==b)ans++;//判断累加}cout<<ans;return 0;
}

总结：直接套用公式优化累加即可

这篇关于【洛谷题解】P1029[普及组]最大公约数和最小公倍数问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---