1.欧拉函数为不完全积性函数

$\phi (n\cdot m)=\phi \left(n\right)\cdot \phi \left(m\right)\cdot \frac{d}{\phi \left(d\right)}其中d=gcd(n,m)$φ(n⋅m)=φ(n)⋅φ(m)⋅φ(d)d​其中d=gcd(n,m)

其实很好理解，假如 $n=2^2\cdot 3^3,m=2^2\cdot 5^3$n=22⋅33,m=22⋅53

那么
$\phi (n\cdot m)=2^2\cdot 3^3\cdot 2^2\cdot 5^5\cdot (1-\frac{1}{2})\cdot (1-\frac{1}{3})\cdot (1-\frac{1}{5})$φ(n⋅m)=22⋅33⋅22⋅55⋅(1−21​)⋅(1−31​)⋅(1−51​)

$\phi \left(n\right)\cdot \phi \left(m\right)=2^2\cdot 3^3\cdot (1-\frac{1}{2})\cdot (1-\frac{1}{3})\cdot 2^2\cdot 5^5\cdot (1-\frac{1}{2})\cdot (1-\frac{1}{5})$φ(n)⋅φ(m)=22⋅33⋅(1−21​)⋅(1−31​)⋅22⋅55⋅(1−21​)⋅(1−51​)

很明显下面的之比上面的多一个 $(1-\frac{1}{2})$(1−21​)，而他其实就是因为 $n$n 和 $m$m 的公共的质因子 $2$2 搞出来的
所以把多余的除掉就行了~