一个数论+组合数学的题目

Question

首先，给出一个整数 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 这个乘幂给它。

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

Answer 1

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

Answer 2

这个问题的另一种描述是：
有一堆多种颜色的球，且相同颜色的球视为等价，各色球数目已知，现在要把这些球分成两堆，要求每一堆至少有1个球，然后问有多少种分法，这个分法数目乘以2就是原题的答案。

Answer 3

这个集合有无限个元素。
你可以取 x=z,y=n*z+1，n为正整数。
当z不等于1时，(x,y)都是这个集合的元素。

Answer 4

你可以取 x=z,y=n*z+1，n为正整数。
当z不等于1时，(x,y)都是这个集合的元素。