题目描述 Description
输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数
条件: 1.P,Q是正整数
2.要求P,Q以x0为最大公约数,以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
输入描述 Input Description
二个正整数x0,y0
输出描述 Output Description
满足条件的所有可能的两个正整数的个数
样例输入 Sample Input
3 60
样例输出 Sample Output
4
暴力求解法：
#include<iostream>
using namespace std;
int Isaccord(int x, int y, int P, int Q)
{
for(int i = x + 1; i <= P; i++)
{//检测是否存在比x更大的公因数
if(P % i == 0 && Q % i == 0)
return 0;
}
for(int i = Q; i <= y - 1; i++)
{//检测是否存在比y更小的公倍数
if(i % P == 0 && i % Q == 0)
return 0;
}
return 1;
}
int main()
{
int x, y;
while(cin >> x >> y)
{
int num = 0;
int P, Q;
for(P = x; P <= y; P++)
{
if(P % x == 0 && y % P == 0)//P是x的倍数，y是P的倍数
{
for(Q = P; Q <= y; Q++)
{
if(Q % x == 0 && y % Q == 0)
{//x是P、Q的公因数，y是P、Q的公倍数
if(Isaccord(x, y, P, Q))//判断是否是最大公因数，最小公倍数
{
if(P == Q)
num ++;
else
num += 2;//P、Q可以交换值作为另一组新的值
}
}
}
}
}
cout << num << endl;
}
}
数论初步求解算法
#include<iostream> using namespace std; int main() { int x, y; while(cin >> x >> y) { int num = 1;//记录不同质因数的个数再包括1，因此初始化为1 if(y % x != 0)//y应当是x的倍数，否则不存在符合条件的P、Q cout << 0 << endl; else { int k = y / x;//为简化问题，将所有的数都除以x int k1 = k; int i = 2; while(i <= k) {//当所有的数都除以x后，找出k的所有质因子的 if(k1 % i == 0) num++;//计算不同的质因子的个数 while(k1 % i == 0) k1 = k1 / i; i++; } /*比如说当k=60时，质因子为 2 , 2, 3, 5再额外加上因子1，（因为P可以等于1*x, 此时Q=k*x），将1,2,2,3,5分成两部份，各部分的乘积分别为P,Q，2和2必定要放在一组 (为满足最小公倍数和最大公因数的条件)，因此不同的组合是(num - 1)*2 */ cout << (num - 1) * 2 << endl; } } }