问个简单的题

回复帖子

@糯米w 2020-02-14 15:58 回复

已知正整数$z$,$x$为$1$到$z$内的整数,$y=\frac{z}{gcd(z,x)}$出现的次数为什么是$\varphi(y)$啊/kel

@CYJian  2020-02-14 16:04 回复 举报

@糯米w 本质上是有多少个 $x \in [1,z]$, $\gcd(x,z)$ 为一个数 $d$。

考虑 $\varphi(x)$ 为 $[1,x]$ 内有多少个数 $val$ 满足 $\gcd(val, x)=1$。

那么考虑 $\gcd(x, z)=d$,等价于 $\gcd(x/d,z/d)=1$。那么也 $\gcd(x, z)=d$ 的数量就是 $\varphi(z/d)=\varphi(y)$。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。