官方链接

oi-wiki

数论函数

数论里的函数 (积性函数, 欧拉函数等), 定义域都是 正整数
… 因为数论一般研究的都是: 自然数.
… 包括下面涉及的所有函数/变量, 都默认是在 (正整数)域的.

所以, 数论函数 也可以看成是一个 数列, 故, 一般写成 $f(n)$, 而不是 $f(x)$

积性函数

若函数 $f(n)$ 满足 $f(1)=1$ 且 $\forall (x,y)互质$ 都有 $f(xy)=f(x)f(y)$，则 $f(n)$ 为 积性函数。
… 可以发现, 积性函数 和 互质 是联系一起的; 只有两者互质, 才符合积性.

若函数 $f(n)$ 满足 $f(1)=1$ 且 $\forall x,y$ 都有 $f(xy)=f(x)f(y)$，则 $f(n)$ 为完全积性函数。

---

积性函数的例子:

• 欧拉函数
• 约数函数: F( x)表示x这个数的约数个数, 他等于: (a1 + 1) * (a2 + 1) * ... (ai为各个质因子的量级)
  … 令Pow( x)为: x的最小的质因子的量级.
  …

  if( i % Prime[ j] == 0){
  	F[ Prime[ j] * i] = F[ i] / Pow[ i] * ( Pow[ i] + 1);
  }
  else{
  	F[ Prime[ j] * i] = F[ i] * 2;
  }
  1
  2
  3
  4
  5
  6

• 约数之和函数: F( x)表示x这个数的 所有约数之和, 他等于: $(1+p_1+p_1^2+...)\ast (1+p_2+p_2^2+...)...$
  令Min( x)为: x的$(1+p_1+p_1^2+...),p_1为其最小质因子$

欧拉函数

欧拉函数 $\varphi (x)$, 定义域为 正整数, 表示: 在[1, x]内, 有多少整数与x互质.

$\varphi (1)=1=1$ (1与任何数互质, 包括自身)
$\varphi (2)=1=1$
$\varphi (3)=1,2=2$
$\varphi (4)=1,3=2$
$\varphi (5)=1,2,3,4=4$

如果x是质数, 显然其$\varphi (x)=x-1$, 除了x, 所有[1, x-1]范围的数 都与x互质.

性质

• 欧拉函数 是 积性函数.
  $\varphi (12)=4,\varphi (2)=1,\varphi (6)=2,\varphi (3)=2,\varphi (4)=2$
  因为3, 4互质, 但是2, 6不是互质的.
  故, $\varphi (3)\ast \varphi (4)=4=\varphi (12)$, 但是, 从$\varphi (2)\ast \varphi (6)$并不能推出$\varphi (12)$, 因为两者不互质.
  证明: 简单证明, 如果你知道欧拉函数的公式的话
  … 对于任意一个数, 其欧拉函数公式为: $\varphi (p_1^{k_1}\ast p_2^{k_2}\ast p_3^{k_3}...)=(p_1^{k_1}\ast p_2^{k_2}\ast p_3^{k_3}...)\ast \frac{p_1-1}{p_1}\ast \frac{p_2-1}{p_2}\ast \frac{p_3-1}{p_3}\ast ...$
  … 合并同类项后, : $(p_1^{k_1}\ast \frac{p_1-1}{p_1})\ast (p_2^{k_2}\ast \frac{p_2-1}{p_2})\ast (p_3^{k_3}\ast \frac{p_3-1}{p_3})...=\varphi (p_1^{k_1})\ast \varphi (p_2^{k_2})\ast \varphi (p_3^{k_3})...$
  … 即: $\varphi (p_1^{k_1}\ast p_2^{k_2}\ast p_3^{k_3}...)=\varphi (p_1^{k_1})\ast \varphi (p_2^{k_2})\ast \varphi (p_3^{k_3})...$
  … 而, $p_1^{k_1},p_2^{k_2},p_3^{k_3}$这些项, 是互相互质的; 即: $\varphi (n),可以拆分成这些项的乘积$
  … 对于$任意的a\ast b=n,且a,b互质$(这是积性函数的前提), a一定是某些项的乘积, b是剩余项的乘积
  … 因此, 满足: $f(a\ast b)=f(a)\ast f(b)$

• 任意数 等于 其所有约数的欧拉函数之和. $n={\sum }_{d|n}^{}\varphi (d)$
  比如, n=10, 其约数为: {1, 2, 5, 10}, 其欧拉函数之和为: $\varphi (1):1+\varphi (2):1+\varphi (5):4+\varphi (10):4=10$
  证明:
  N为任意正整数 (在以下证明中, N可以当成是个常数), 证明: $N={\sum }_{d|N}^{}\varphi (d)$
  令 $C(x)为:\forall i\in [1,N],且满足:gcd(i,N)=x条件的,i的个数$
  … 结论一: $N={\sum }_{i=1}^{N}C(i)$
  … 证明: 因为对任意的 $i\in [1,N]$ , gcd( i, N)的值 是唯一的; 而且gcd( i, N)的值 都是在[1, N]范围内.
  … 结论二: $N={\sum }_{i|N}C(i)$
  … 证明: 所有的gcd( i, N)一定都是N的约数.
  … … 比如, N = 10, 则 C ( 1 ) : { 1 , 3 , 7 , 9 } = 4 , C ( 2 ) : { 2 , 4 , 6 , 8 } = 4 , C ( 5 ) : { 5 } = 1 , C ( 10 ) : { 10 } = 1 C(1): \{ 1, 3, 7, 9\} = 4, \quad C( 2): \{ 2, 4, 6, 8\} = 4, \quad C( 5) : \{ 5\} = 1, \quad C( 10) : \{ 10\} = 1 C(1):{1,3,7,9}=4,C(2):{2,4,6,8}=4,C(5):{5}=1,C(10):{10}=1
  … … 其他的 $C(3,4,6,7,8,9)=0$
  … 结论三: $C(i)=\varphi (N/i)$
  … 证明: 对于 C ( i ) = k , 其集合元素为 { c 1 , c 2 , . . . , c k } C( i) = k, 其集合元素为\{ c1, c2, ..., ck \} C(i)=k,其集合元素为{c1,c2,...,ck}, 均有: gcd( cj, N) = i
  … … 此时, 左右侧同除i, $gcd(\frac{cj}{i},\frac{N}{i})=1$(两者都是可以整除的), 此时集合变成: { c 1 i , c 2 i , . . . , c k i } \{ \frac{ c1}{ i}, \frac{ c2}{ i}, ..., \frac{ ck}{ i} \} {ic1​,ic2​,...,ick​}
  … … 因为$cj\in [1,N],所以:\frac{cj}{i}\in [1,\frac{N}{i}]$, 因此, 这个 { c 1 i , c 2 i , . . . , c k i } \{ \frac{ c1}{ i}, \frac{ c2}{ i}, ..., \frac{ ck}{ i} \} {ic1​,ic2​,...,ick​}集合个数, 就等于 $\varphi (N/i)$
  … … 此时我们得到: $N={\sum }_{i|N}\varphi (\frac{N}{i})$
  … 结论四: $N={\sum }_{i|N}\varphi (i)$
  … 证明: 一个数的所有约数集合, 10: 1, 2, 5, 10, $\varphi (10)+\varphi (5)+\varphi (2)+\varphi (1)=\varphi (1)+\varphi (2)+\varphi (5)+\varphi (10)$
  … … 故, ${\sum }_{i|N}\varphi (\frac{N}{i})={\sum }_{i|N}\varphi (i)$

• 若$N=p^k,其中p为质数$, 则$\varphi (N)=N-p^{k-1}$
  … (一般常用$\varphi (p^k)=p^k\ast \frac{p-1}{p}$这个公式)
  对于N, 他和不互质的数, 只有: $p,2p,3p,...,kp$ (注意, 不是p, p^2, p^3, ..., p^k)
  关键是k等于多少呢?
  … 即在一个有N个元素的数组中, 从左到右, 每p个 拿一个数, 总共是多少个呢?
  … 总共有$\frac{N}{p}$个
  因此, 与N不互质的个数有: $\frac{N}{p}=p^{k-1}$

• 对任意的$N=p_1^{k_1}\ast p_2^{k_2}\ast p_3^{k_3}...$, 则 $\varphi (N)=N\ast \frac{p_1-1}{p_1}\ast \frac{p_2-1}{p_2}\ast \frac{p_3-1}{p_3}\ast ...$
  证明: 因为欧拉函数是积性函数, 我们将其拆分成: $p_1^{k_1},p_2^{k_2},p_3^{k_3},...$ 这些项
  这些项 他们是互相互质的, 所以, 满足 积性函数的拆分条件.
  $\varphi (N)=\varphi (p_1^{k_1})\ast \varphi (p_2^{k_2})\ast \varphi (p_3^{k_3})\ast ...$
  根据上条性质, $\varphi (p_1^{k_1})=p_1^{k_1}\ast \frac{p_1-1}{p_1}$, 依次带入即可.

例题

• https://blog.csdn.net/weixin_42712593/article/details/126301107
  线性筛 欧拉函数.

• https://blog.csdn.net/weixin_42712593/article/details/126306323
  线性筛 欧拉函数.