[01NOIP普及组] 最大公约数与最小公倍数

skystars

【题目描述】
二个正整数x0,y0(2≤x0≤100000,2≤y0≤1000000),求满足下列条件的P,Q的个数。

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

【输入】
输入x0和y0

【输出】
满足条件的所有可能的两个正整数的个数

【输入样例】
3 60
【输出样例】
4
【提示】
样例说明:此时的P Q分别为：
3 60
15 12
12 15
60 3

【代码】

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

inline int gcd(int x, int y)
{
        if (y == 0) return x;
        return gcd(y, x % y);
}

int main()
{
        int x0, y0, t, s = 0, del = 0;
        cin >> x0 >> y0;
        t = x0 * y0;
        int j;
        for (register int i = 2; i <= sqrt(t); i++) {
                j = t / i;
                if (gcd(i, j) == x0 && i * j / gcd(i, j) == y0) {
                        s++;
                        if (i == j) del = 1;
                }
        }
        cout << s*2-del;
}