求满足条件的正整数对的个数 - C++11实现

{"title":"题目描述\n输入两个正整数 x,y，求出满足下列条件的P和Q的个数：\n\n P和Q是正整数。\n\n 要求P和Q以 x 为最大公约数，以 y 为最小公倍数。\n\n 试求：满足条件的所有可能的P和Q的个数。\n\n 输入格式\n一行两个正整数 x,y。\n\n 输出格式\n一行一个数，表示求出满足条件的 两个正整数P，Q的个数。\n\n 样例\n样例输入 #1\n3 60\n样例输出 #1\n4\nc++11实现内容：分析：\n根据题意，P和Q的最大公约数是x，最小公倍数是y，即P和Q的最大公约数是x，且P和Q的乘积是xy。\n\n 设P=xm，Q=xn，则P和Q的最大公约数是x，且P和Q的乘积是xy，即xmxn=xy，解得mn=y。\n\n 因此，问题就转化为求满足mn=y的正整数对(m,n)的个数。\n\n 解题思路：\n首先，可以根据y的因子来求满足条件的m和n的个数。\n\n 1. 首先求出y的所有因子，保存在一个数组中。\n\n 2. 遍历这个数组，假设当前的因子是f，那么满足条件的m=n=f的个数就是f的因子个数的平方减去1，即(f的因子个数的平方减去1)加到结果中。\n\n 3. 最后，结果就是满足条件的m和n的个数。\n\n 实现代码如下：\n\n #include \n #include \n #include \n using namespace std;\n\n // 求一个数的因子\n vector getFactors(int num) {\n vector factors;\n for (int i = 1; i <= sqrt(num); i++) {\n if (num % i == 0) {\n factors.push_back(i);\n if (i != num/i) {\n factors.push_back(num/i);\n }\n }\n }\n return factors;\n }\n\n int main() {\n int x, y;\n cin >> x >> y;\n\n // 求y的所有因子\n vector factors = getFactors(y);\n\n int count = 0;\n // 遍历因子\n for (int i = 0; i < factors.size(); i++) {\n int factor = factors[i];\n // 满足条件的m和n的个数就是因子个数的平方减去1\n count += pow(2, getFactors(factor).size()) - 1;\n }\n\n cout << count << endl;\n\n return 0;\n }\n\n