发表于 2019-05-27 |更新于 2019-05-27 |ACM学习笔记数学
对于一个离散函数$f(x), x\in Z^+$ , 如果$\forall \gcd(a,b)=1$都有$f(a\cdot b)=f(a)\cdot f(b)$, 则称函数$f(x)$为积性函数.
对于一个离散函数$f(x), x\in Z^+$ , 如果$\forall a,b\in Z^+$都有$f(a\cdot b)=f(a)\cdot f(b)$, 则称函数$f(x)$为完全积性函数.
我们根据积性函数的定义,其实只要我们计算出了所有素数的幂的函数值,则任何其他$f(x)$都可以快速获取.
$\phi(n)$就是小于等于n,且