样例没过求调

P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

Miracle_InDream @ 2024-02-05 10:30:54

#include<bits/stdc++.h>
using namespace std;
bool ss(int a)
{
    for(int i=2;i<a/2;i++)
    {
        if(a%i==0)
        {
            return 0;
        }
    }
    return 1;
}
int zdgbs(int a,int b)
{
    int m=1; 
    for(int i=2;i<a;i++)
    {
        if(ss(i)&&a%i==0&&b%i==0)
        {
            m*=i;
            a/=i;
            b/=i;
        }
    }
    m*=a;
    m*=b;
    return m;
}
int zxgys(int a,int b)
{
    if(b==0)
    {
        return a;
    }
    return zxgys(b,a%b);
}
int main()
{
    int x,y;
    cin>>x>>y;
    int ans=0;
    for(int i=x;i<y;i++)
    {
        for(int j=y;j>i;j--)
        {
            if(zxgys(i,j)==x&&zdgbs(i,j)==y)
            {
                ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}

by Somnus_Love @ 2024-02-05 17:35:47

@shooting__star (你不会gcd吗)


by lutaoquan2012 @ 2024-02-05 17:35:49

@shooting__star 原本14行的代码硬生生被你写出了这么多行


by lutaoquan2012 @ 2024-02-05 17:37:21

gcd在数据库里面有函数啊


by 半只蒟蒻 @ 2024-02-05 17:48:37

@shooting__star 思路有问题

你需要注意到到两个数的最小公倍数和最大公约数的一个性质

假设 g=gcd(a,b),l=lcm(a,b)

那么有 g*l=a*b

然后枚举 g*l 的因子就行了,O(\sqrt{x_0*y_0})


by ZettaByte @ 2024-02-05 18:00:06

逆天。


by 半只蒟蒻 @ 2024-02-05 18:01:32

@ZettaByte ?


by ZettaByte @ 2024-02-05 18:02:27

@半只蒟蒻 ?干啥


by Miracle_InDream @ 2024-02-05 21:05:49

哦草直接gcd?


|