POJ1091 - 跳蚤

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

完整的题目描述在这里

题目给出了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})$

至此,问题解决。


本作品遵循“署名-非商业性使用-相同方式共享 3.0 Unported”协议,转载请注明来自richard-desktop
Creative Commons License

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter