POJ1091 - 跳蚤

张文泰 posted @ 2010年1月17日 07:51 in Art of Science with tags acm POJ 数论欧拉函数 , 4499 阅读

完整的题目描述在这里。

题目给出了n和m，要求出满足最大公约数(x₁,x₂,...,x_n,m)=1且x_i不超过m的这样的x₁,...,x_n的组数。x_i都是正整数。

如果n=1，那就是求欧拉函数 $\varphi(m)$ 。我们可以联想其形式： $\varphi(m)=m\prod_{p|m}(1-\frac{1}{p})$ 。那么当n>1时我们也来类比一下相对应的公式。

令 $\varphi(m,n)$ 表示题目中所要求的答案。我们发现，当m为素数时， $\varphi(m,n)=m^n-1$ 。这是显然的，因为除了(m,m,...,m,m)这一组数字以外，其余的都是可行的解。那么m不为素数时，我们把m的各个素因数分开考虑。如果某个素因数被n个数所共有，那么一共就少了 $m^n\frac{1}{p^n}$ 种方案，考察m所有的素因数，我们得到 $\varphi(m,n)=m^n\prod_{p|m}(1-\frac{1}{p^n})$ 。