Python3 算法：求满足最大公约数和最小公倍数条件的整数对个数

问题描述：

输入两个正整数 x, y，输出满足以下条件的整数对 (a, b) 的总数：

(1) a, b 的最大公约数是 x (2) a, b 的最小公倍数是 y

(输入数据会保证使用暴力遍历的解法无法在给定时间内得到答案)

**输入：**两个正整数 x, y，用空格隔开

**输出：**所有满足条件的整数对 (a, b) 的总个数

输入示例：

3 60

输出示例：

解题思路：

根据题目要求，我们需要找到满足条件的整数对 (a, b) 的总个数。根据最大公约数和最小公倍数的性质，我们可以知道，满足条件的整数对 (a, b) 的最小公倍数 y 是 x 的倍数，即 y = kx。

我们可以遍历 k 的取值范围，然后计算出 a 和 b 的值，判断是否满足条件。如果满足条件，计数器加 1。最后输出计数器的值即可。

具体实现如下：

def count_integer_pairs(x, y):
    count = 0
    for k in range(1, y//x + 1):
        a = k * x
        b = y // k
        if a * b == y:
            count += 1
    return count

# 读取输入的两个正整数
x, y = map(int, input().split())
# 调用函数计算满足条件的整数对的总个数
result = count_integer_pairs(x, y)
# 输出结果
print(result)

复杂度分析：

假设 x 和 y 的位数分别为 n 和 m，那么时间复杂度为 O(m)。在最坏情况下，m 的取值为 log(y)，所以时间复杂度为 O(log(y))。空间复杂度为 O(1)。