题目描述
输入2个正整数x0,y0(2≤x0<100000,2≤y0<=1000000),求出满足下列条件的P,Q的个数
条件:
P,Q是正整数
要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的2个正整数的个数.
输入格式
2个正整数x0,y0
输出格式
1个数，表示求出满足条件的P,Q的个数
输入输出样例
输入 #1
3 60
输出 #1
4
说明/提示
P,Q有4种
1、3,60
2、15,12
3、12,15
4、60,3
思路
整个数论这一块都是些奇奇怪怪的知识emmmm。
最大公约数是x0，最小公倍数为y0，所以设这两个数为x0k1 , x0k2 (其中k1,k2互质）。由题意得：x0 * k1 * k2 = y0,所以 k1*k2 = y0 / x0 (当然如果y0 / x0 除不尽的话 ，输出0）
源码
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
return a % b == 0 ? b : gcd(b, a % b);//判断是否互质（最大公约数是否为1）
}
int main()
{
int n, m, sum = 0;
cin >> n >> m;
if (m % n != 0)
{
cout << 0;
return 0;
}
int temp = m / n;
for (int i = 1; i <= floor(sqrt(temp)); i++)
{
if (temp % i == 0 && gcd(i, temp / i) == 1)
sum += 2;
}
cout << sum;
return 0;
}
