Vijos P1131 — 最小公倍数和最大公约数问题

题目

输入二个正整数x0,y0(2≤x0≤100000，2≤y0≤1000000)，求出满足下列条件的P、Q的个数。

条件:1.P、Q是正整数
2.要求P、Q以x0为最大公约数，以y0为最小公倍数。

试求，满足条件的所有可能的两个正整数的个数。

题目链接

https://vijos.org/p/1131

输入数据

两个正整数

输出数据

满足条件的所有可能的两个正整数的个数

样例输入

3 60

样例输出

4

提示

说明：(不用输出)此时的 P Q 分别为：
3 60
15 12
12 15
60 3
所以，满足条件的所有可能的两个正整数的个数共4种

来源

noip2001普及组第二题

问题分析

由于最大公约数为 x0，最小公倍数为 y0，所以 x0 <= p,q <= y0；另外，两个数的乘积等于它们的最大公约数(gcd)与最小公倍数(lcm)之积，即a * b = gcd(a, b) * lcm(a, b)
所以只要枚举p，在x0 * y0 % p == 0的情况下，判断 gcd(x0 * y0 / p, p) == x0 即可。gcd()函数使用辗转相除法。

AC代码

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int main()
{
    int x0, y0, p, q, t, ans = 0;
    cin >> x0 >> y0;
    t = x0 * y0;
    for (p = x0; p <= y0; p++)
    {
        q = t / p;
        if (p * q == t)
        {
            if (gcd(p, q) == x0)
                ans++;
        }
    }
    cout << ans << endl;
    return 0;
}