【一个数论+组合数学的题目首先,给出一个整数z.要求求出一个-查字典问答网

来自刘淑霞的问题

　　【一个数论+组合数学的题目首先,给出一个整数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这个乘幂给它.

　　我的组合数学学得不好（其实是没学过）.所以希望有高人能解决这个问题.

1回答

2020-01-30 01:53

我要回答

请先登录

曹长修

　　{(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)]

2020-01-30 01:55:43