关于一道数论的问题!高手解答
问题描述：
关于一道数论的问题!高手解答
试求有序正整数对x、y的个数,使(x,y)=5![x,y]=50!
题目不难,希望高手能给出很简洁的做法,不胜感激,奖赏可以高追加,非诚勿扰!
答
由(x,y)=5!,可设x=(5!)a,y=(5!)b.则(a,b)=(x,y)/5!=1,即a和b互素,所以[a,b]=ab.所以[x,y]=(5!)[a,b]=(5!)ab.所以问题等价于：
求有序正整数对a,b的个数,使得a和b互素,且ab=50!/5!=6*7*8*...*50.
引理：设正整数N有k个素因子,则恰有2^k个有序正整数对a,b,使得a和b互素,且ab=N.
证明：设N=(p1^n1)(p2^n2)...(pk^nk).由条件易知若pi|a,则pi^ni整除a（否则pi|a且pi|b）.所以a总等于某些pi^ni的乘积,而b等于N/a.这样的不同取法恰好一一对应于集合{p1^n1,p2^n2,...,pk^nk}的不同子集（空集对应于a=1,b=N；全集对应于a=N,b=1）,共有2^k个.
6*7*8*...*50的素因子有：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,共15个.所以所求正整数对的个数=2^15=32768