2.要求PQ以x0为最大公约数以y0为最小公倍数.
试求:满足条件的所有可能的两个正整数的个数.
题目给出了gcd(pq)和lcm(pq),让我们求解p,q的正整数解数.
则两边同时除G
则原问题就变为了x*y=s 并且gcd(x y)=1
因式分解就可以得到.
然后列举s的因数x,得到另一个因数y,判断gcd(x.y)是否等于1即可.详见程式1
这里讲一个更有数学味的算法,希望大家看完.
按照上面的分析,无非就是把问题转化成为了求S的因数集合中,两两互质的数对的个数.
设 x是s的一个因数,相对的因数是y=s/x
s总共有n个质因数,那么答案一定是 2^n
这里用语言简单说明一下,通过刚才的证明,有xy=s,所以 x 必为 b阵列中若干不相同元素的乘积,那么不是x因数的 b阵列中的元素,一定是y的因数,那么考虑会选择哪几个元素相乘得到x,必然用二进位制加以列举.