作业帮一个数论+组合数学的题目
来源：学生作业帮 编辑：拍题作业网作业帮 分类：综合作业 时间：2024/05/20 00:33:36
一个数论+组合数学的题目
首先,给出一个整数 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 这个乘幂给它.
我的组合数学学得不好（其实是没学过）.所以希望有高人能解决这个问题.
首先,给出一个整数 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)]
假设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)]