使用Python3编写程序计算满足最大公约数和最小公倍数条件的整数对数量

"使用Python3编写程序计算满足最大公约数和最小公倍数条件的整数对数量"\n\n输入两个正整数x,y，输出满足以下条件的整数对(a,b)的总数：\n（1）a,b的最大公约数是x\n（2）a,b的最小公倍数是y\n(输入数据会保证使用暴力遍历的解法无法在给定时间内得到答案）\n\n输入：两个正整数x,y，用空格隔开\n输出：所有满足条件的整数对(a,b)的总个数\n\n输入示例：\n3 60\n输出示例：\n4\n\n解题思路：\n根据题目要求，我们需要找出满足条件的整数对(a,b)的总数，其中a,b的最大公约数是x，最小公倍数是y。\n\n我们可以通过分解最大公约数x和最小公倍数y来求解。\n\n首先，我们求出x的所有因数。对于x的每个因数d，我们可以知道d一定是a的因数，因此a可以表示为dk，其中k是一个整数。\n\n接下来，我们计算最小公倍数y的所有因数。对于y的每个因数f，我们可以知道b可以表示为fl，其中l是一个整数。\n\n由于a和b的最大公约数是x，最小公倍数是y，所以我们可以得到dk和fl的最大公约数是x，最小公倍数是y。\n\n所以，我们只需要找出x的因数d和y的因数f的组合即可得到满足条件的整数对(a,b)。\n\n具体实现如下：\n\npython\ndef gcd(a, b):\n while b != 0:\n a, b = b, a % b\n return a\n\ndef count_integer_pairs(x, y):\n # 求出x的所有因数\n factors_x = []\n for i in range(1, int(x**0.5) + 1):\n if x % i == 0:\n factors_x.append(i)\n if i != x // i:\n factors_x.append(x // i)\n \n # 求出y的所有因数\n factors_y = []\n for i in range(1, int(y**0.5) + 1):\n if y % i == 0:\n factors_y.append(i)\n if i != y // i:\n factors_y.append(y // i)\n \n count = 0\n for d in factors_x:\n for f in factors_y:\n if gcd(d, f) == x:\n count += 1\n \n return count\n\n# 获取输入\nx, y = map(int, input().split())\n\n# 输出结果\nprint(count_integer_pairs(x, y))\n\n\n复杂度分析：\n- 求x的因数的时间复杂度为O(sqrt(x))，求y的因数的时间复杂度为O(sqrt(y))。\n- 遍历x和y的因数的组合的时间复杂度为O(sqrt(x) * sqrt(y))。\n- 求最大公约数的时间复杂度为O(log(min(d, f)))。\n- 总时间复杂度为O(sqrt(x) * sqrt(y) * log(min(d, f)))。