问题标题：
【一个数论+组合数学的题目首先,给出一个整数z.要求求出一个集合的元素个数,这个集合是：{(x,y)|xy|z,gcd(x,y)=1}意思就是说,求出一个点集的元素个数,对于其中每个元素(x,y)有：xy能够整】
问题描述：
一个数论+组合数学的题目
首先,给出一个整数z.
要求求出一个集合的元素个数,这个集合是：
{(x,y)|xy|z,gcd(x,y)=1}
意思就是说,求出一个点集的元素个数,对于其中每个元素(x,y)有：
xy能够整除z并且x和y互质.
再次提醒,是求集合元素的个数.
-----------------------------------------------------
由于是编程求解,我目前的解法是,将z表示成如下形式：
z=1*2^p1*3^p2*5^p3*7^p4*...
其中除了第一个项为1之外,其余各项底数皆为质数.还有,p(m)是非负整数.
之后,若要求集合元素个数,那么,这要利用到组合数学里面的东西,之后还要特别考虑一下那个第一项,因为它不是质数,而且,没有p0这个乘幂给它.
我的组合数学学得不好（其实是没学过）.所以希望有高人能解决这个问题.
曹长修回答：
{(x,y)|xy|z,gcd(x,y)=1}
假设z=1*2^p1*3^p2*5^p3*7^p4*……*an^pn
那么根据z的形式,通过判断p>0,可以得到z的k个最小因子,
假设为：a1、a2、a3、a4……ak
那么从这k个因子中选取i个因子组成x,再考虑因子的幂数,共有：
∏pi×∑C(k,i)(i=0,k),i取0,就是x=1
由于gcd(x,y)=1
那么y只能从剩余的k-i个因子选取j个组成,再考虑因子的幂数,
∏pj×∑C(k-i,j)(j=1,k-i)
显然x≠y,另外考虑x和y调换,再乘以2
所以,{x,y}集合的个数＝2×{∏pi×∑C(k,i)}×{∏pj×∑C(k-i,j)}[(i=0,k),(j=1,k-i)]
查看更多
