洛谷P1209-最大公约数与最小公倍数问题

时间：2021-06-22 22:17:43

一个萌新的成长之路

Discription

  • 输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数

条件:
1.P,Q是正整数
2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.

Input&Output

输入格式：

  • 二个正整数x0,y0

输出格式：

  • 一个数，表示求出满足条件的P,Q的个数

Example

Input:

3 60

Output:

4

Solution

  • 本题并不难解，由于x为P，Q的最大公约数，所以枚举x的倍数即可。此外，又有两数的乘积除以其最大公约数等于其最小公倍数，得到判断条件。需要注意的是，由于类似3 60和60 3属于两组解，输出时应乘以2；

  • 代码如下：

    #include<iostream>
#include<algorithm>
using namespace std;
int x, y, ans = 0;
bool sig = true;
int gcd(int a, int b)
{
if (a < b)swap(a, b);
if (b == 0)return a;
else return gcd(b, a%b);
}
void sch()
{
for (int i = 1;i*x <= y;i++)//枚举倍数
{
    for (int j = i;j*x <= y;j++)
    {
        if (i*x*j == y&&gcd(i, j) == 1)ans++;//这里做了点处理，i*x*j*x/x可以约去x.
    }
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>x>>y;
sch();
cout<<2*ans;
return 0;
}

  • 然而本萌新意识到了一个问题：对于类似x=60 y=60的输入，应当只有一组解，实测却输出了2（尽管代码AC了），为了宇宙的和平与正义！瑟(wen)瑟(le)发(da)抖(lao)之后，得到了：

    对于x==y的输入，有且仅有一组解满足条件。

  • 于是，大概特判一发就可以了？

    if(x==y)cout<<1,return 0;

  • Dec,09,2017 Sat

相关文章