[问题描述]
输入二个正整数x0,y0(2≤x0≤100000，2≤y0≤1000000)，求出满足下列条件的P、Q的个数。
条件:1、P、Q是正整数
2、要求P、Q以xO为最大公约数，以yO为最小公倍数。
试求，满足条件的所有可能的两个正整数的个数。
[样例]
输入：x0=3 y0=60
输出：4
说明：(不用输出)此时的 P Q 分别为，
3 60
15 12
12 15
60 3
所以，满足条件的所有可能的两个正整数的个数共4种。
知识准备：
若p,q的最大公约数为x0,则：
p%x0=0,q%x0=0
假设 p1=p/x0 q1=q/x0
进行如下推导：
1。如果p1=q1,则根据最大公约数的定义，p1=q1=1,p=q=x0,根据最小公倍数的定义，p=q=y0,则 x0=y0=p=q
2.如果p1!=q1,根据最大公约数的定义，p1与q1除了1以外没有其他相同的因子，即p1,q1互质。
3.根据最小公倍数的定义，y0=pq/x0, 又p1=p/x0,q1=q/x0,则可推出如下的等式：p1q1=y0/x0.
根据以上分析，可以推出以下算法：
1。如果y0%x0!=0,则p,q不存在。
2。如果y0=x0,则存在一组p,q,且p=q=x0=y0
3. 在1～y0/x0之间查找满足p1q1=y0/x0且p1,q1互质的数据对。
参考程序如下：
#include<iostream>
#include<cstdio>
using namespace std;
long x,y,p,q,i,s;
int hz(long p,long q)//判断p,q互质
{
long j;
for(j=2;j<=p;j++)
if(p%j==0&&q%j==0)
return 0;
return 1;
}
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while(cin>>x>>y)
{
if(y%x!=0)
cout<<0<<endl;
else if(y==x)cout<<1<<endl;
else
{
s=0;
i=y/x;
for(p=1;p<=i;p++)
for(q=1;q<=i;q++)
if((p*q==y/x)&&hz(p,q))
s++;
cout<<s<<endl;
}
}
return 0;
}
二。对算法的改进
1．猜想
根据前面的分析：如果p,q的最大公约数为x,最小公倍数为y,则只要查找满足乘积为y/x且互质的p1,q1数据对就可以了。这样的数据对个数有没有规律呢？
猜想：设y0/x0的质因子个数为k,则满足条件的p,q对个数为2^k,即集合中子集合的数目。
证明：
假设y0/x0有k个质因子，y0/x0=a1*a1*…ak (ai是质数，算术基本定理)
要使得p1*q1=y0/x0,且p1,q1互质，则p1,q1不能含有相同的的质因子，因此p1,q1的选择总数为
如何统计整数s的质因子个数k?最简单的方法是线性查找。从2开始依次累加，第一个能整除s的数据必然为质因子，通过循环整除操作排除该质因子后，下一个能整除s的数据还是质因子。
算法如下：
1． i=2;
2． While (s%i!=0) s++;
3． K++;
4． While (s%i==0) s=s/i;
5． 继续执行语句2。
参考程序如下：
#include<iostream>
#include<cstdio>
using namespace std;
long x,y,p,q,i,s,j,k;
long total;//保存2^k
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while(cin>>x>>y)
{
if(y%x!=0)
cout<<0<<endl;
else if(y==x)cout<<1<<endl;
else
{
s=0;
i=y/x;
j=2;
while(i>1)
{
while(i%j!=0) j++;
s++;
while(i%j==0) i=i/j;
}
total=1;
for(j=1;j<=s;j++)
total*=2; //计算2^k
cout<<total<<endl;
}
}
return 0;
}