3 2 1 上題目鏈接：
P1029 [NOIP2001 普及組] 最大公約數(shù)和最小公倍數(shù)問題
本小蒟蒻的原始思路就是枚舉所有范圍內(nèi)的數(shù)，分別求出他們的最大公約數(shù)和最小公倍數(shù)，再看是否滿足題意。
于是就有了以下一言難盡的東西(；′⌒`)↓
#include <stdio.h>
int main()
{
int x,y,count;
scanf("%d%d",&x,&y);
for(int i=x;i<=y;i+=x)//i+=x是因?yàn)榍蟪鰜淼臄?shù)肯定是x的倍數(shù)，所以就以x為增量了
{
for(int j=x;j<=y;j+=x)
{
int m=i,n=j,t;
while(m%n)//求最大公約數(shù)
{
t=m%n;
m=n;
n=t;
}
if(n==x&&i*j==x*y)//i*j==x*y是因?yàn)樽钚」稊?shù)等于兩個(gè)數(shù)的乘積除以最大公約數(shù)
count++;
}
}
printf("%d",count);
return 0;
}
皇天不負(fù)有心人，收到了2個(gè)TLE，其他全WA
自我反省大佬們的題解，做了以下優(yōu)化↓
#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)//減少循環(huán)次數(shù)
{
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，因?yàn)閕和j倒過來又是一種情況
}
}
printf("%d",count);
return 0;
}
注：
- 補(bǔ)充上遺漏的特解（
不然也會(huì)錯(cuò)），x=y時(shí)，只會(huì)出現(xiàn)一次 - x=y時(shí)，i=j=x=y，在此之后就都是倒過來重復(fù)的情況，所以循環(huán)到√(x*y)即可，減少了循環(huán)次數(shù)
- 綜上，count每次+2，特解時(shí)count-1即可
不知道為什么就能AC了，有大佬說需要用long long，不然會(huì)爆，但我沒有(⊙o⊙)？文章來源：http://www.zghlxwxcb.cn/news/detail-825019.html
覺得還有一個(gè)方法很好，遞歸輾轉(zhuǎn)相除求最大公約數(shù)：文章來源地址http://www.zghlxwxcb.cn/news/detail-825019.html
int gcd(int n,int m)
{
if(n%m==0)
return m;
else
return gcd(m,n%m);
}
到了這里，關(guān)于P1029 最大公約數(shù)和最小公倍數(shù)問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
