Jan 17

POJ1091 - 跳蚤

Art of Science 0 Comments

完整的题目描述在这里。

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

如果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})$。

至此，问题解决。