洛谷-P1029 最大公约数和最小公倍数问题(GCD模板题)

题目描述

输入两个正整数 x_0, y_0x0,y0，求出满足下列条件的 P, QP,Q 的个数：

1. P,QP,Q 是正整数。
2. 要求 P, QP,Q 以 x_0x0 为最大公约数，以 y_0y0 为最小公倍数。

试求：满足条件的所有可能的 P, QP,Q 的个数。

输入格式

一行两个正整数 x_0, y_0x0,y0。

输出格式

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

输入输出样例

输入 #1

3 60

输出 #1

4

说明/提示

P,QP,Q 有 44 种：

1. 3, 60。
2. 15, 12。
3. 12, 15。
4. 60, 3。

对于 100% 的数据，2 \le x_0, y_0 \le {10}^52≤x0,y0≤105。

---

#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <cctype>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

inline int GCD(int a, int b)
{
    return b == 0 ? a : GCD(b, a % b);
}

int solve(int x, int y)
{
    if (y < x || y % x != 0) return 0;
    int res = y / x;
    int cnt = 0;
    for (int i = 1; i <= res; ++i) {
        if (res % i == 0 && GCD(i, res / i) == 1) ++cnt;
    }

    return cnt;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int x, y;
    cin >> x >> y;

    cout << solve(x, y) << endl;

    return 0;
}

根据GCD和LCM的求法可知： $$ P = x \times a \ Q = x \times b \ y = x \times a \times b $$ 其中a,b互质，所以很容易得知a * b的结果，然后有多少个互质的a和b，那么就存在多少对P和Q。

---

使用“二进制”优化的GCD版本：

#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <cctype>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

int GCD(int x, int y)
{
    if (!x) return y; 
    if (!y) return x;
    int num1 = 0, num2 = 0;
    for ( ; (x & 1) == 0; ++num1) x >>= 1; //去掉x里面的2并计数
    for ( ; (y & 1) == 0; ++num2) y >>= 1; //去掉y里面的2并计数
    if (num2 < num1) num1 = num2; //x和y里面共同包含的因子2的个数

    //此时x和y都是奇数
    while (true) {
        if (y > x) x ^= y ^= x ^= y; //位运算加速数值交换
        //判断是否符合退出条件，顺便计算GCD(x - y, y)
        if ((x -= y) == 0) return y <<= num1; //x和y相等的情况，输出结果
        //两个奇数相减后x变为偶数，需要去掉2
        while ((x & 1) == 0) x >>= 1;
    }
}

// inline int GCD(int a, int b)
// {
//  return b == 0 ? a : GCD(b, a % b);
// }

int solve(int x, int y)
{
    if (y < x || y % x != 0) return 0;
    int res = y / x;
    int cnt = 0;
    for (int i = 1; i <= res; ++i) {
        if (res % i == 0 && GCD(i, res / i) == 1) ++cnt;
    }

    return cnt;
}

int main()
{
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

    int x, y;
    cin >> x >> y;

    cout << solve(x, y) << endl;

    return 0;
}