P1029 最大公约数和最小公倍数问题

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;
}

注:

  1. 补充上遗漏的特解(不然也会错),x=y时,只会出现一次
  2. x=y时,i=j=x=y,在此之后就都是倒过来重复的情况,所以循环到√(x*y)即可,减少了循环次数
  3. 综上,count每次+2,特解时count-1即可

不知道为什么就能AC了,有大佬说需要用long long,不然会爆,但我没有(⊙o⊙)?

觉得还有一个方法很好,递归辗转相除求最大公约数:

int gcd(int n,int m)
{
    if(n%m==0)
	return m;
    else 
	return gcd(m,n%m);
}

热门相关:24岁尹律的性感乳房   OUT   小媳妇   小姨子对姐夫的性幻想   武士传奇 下