3 2 1 上题目链接：
P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
本小蒟蒻的原始思路就是枚举所有范围内的数，分别求出他们的最大公约数和最小公倍数，再看是否满足题意。
于是就有了以下一言难尽的东西(；′⌒`)↓
#include <stdio.h>
int main()
{
int x,y,count;
scanf("%d%d",&x,&y);
for(int i=x;i<=y;i+=x)//i+=x是因为求出来的数肯定是x的倍数，所以就以x为增量了
{
for(int j=x;j<=y;j+=x)
{
int m=i,n=j,t;
while(m%n)//求最大公约数
{
t=m%n;
m=n;
n=t;
}
if(n==x&&i*j==x*y)//i*j==x*y是因为最小公倍数等于两个数的乘积除以最大公约数
count++;
}
}
printf("%d",count);
return 0;
}
皇天不负有心人，收到了2个TLE，其他全WA
自我反省大佬们的题解，做了以下优化↓
#include <stdio.h>
#include <math.h>
int main()
{
int x,y,count=0;
scanf("%d%d",&x,&y);
if(x==y)//特解
count--;
for(int i=x;i<=sqrt(x*y);i+=x)//减少循环次数
{
for(int j=x;j<=y;j+=x)
{
int m=i,n=j,t;
while(m%n)
{
t=m%n;
m=n;
n=t;
}
if(n==x&&i*j==x*y)
count+=2;//每次加2，因为i和j倒过来又是一种情况
}
}
printf("%d",count);
return 0;
}
注：
- 补充上遗漏的特解（
不然也会错），x=y时，只会出现一次 - x=y时，i=j=x=y，在此之后就都是倒过来重复的情况，所以循环到√(x*y)即可，减少了循环次数
- 综上，count每次+2，特解时count-1即可
不知道为什么就能AC了，有大佬说需要用long long，不然会爆，但我没有(⊙o⊙)？文章来源：https://www.toymoban.com/news/detail-825019.html
觉得还有一个方法很好，递归辗转相除求最大公约数：文章来源地址https://www.toymoban.com/news/detail-825019.html
int gcd(int n,int m)
{
if(n%m==0)
return m;
else
return gcd(m,n%m);
}
到了这里，关于P1029 最大公约数和最小公倍数问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
