欧拉函数

emptysetvvvv · 2019-10-03 14:09:02 · 个人记录

• 【概念】欧拉函数\varphi：n以内与n互质的数的个数，其实质为简化剩余系的大小。

特别的，\varphi(1)=1.

1\ [欧拉函数的基本性质]

• 【性质】

1. \varphi(p)=p-1，p为质数.

证明略。

2. \varphi(p^k)=p^k-p^{k-1}，当k=1时，即为性质1.

证明：仅有的因子 p 均匀分布，因此p^k个数中有\displaystyle\frac{1}{p}的数不互质。

3. \forall n>2,\quad\varphi(n)为偶数.

证明：∵\gcd(n,m)=\gcd(n,n-m)，n>2 且为偶数时 \gcd(n,n/2)\ne0，即 m\ne n-m.

∴ n 与 m 互质 \Leftrightarrow n 与 n-m 互质，与 n 互质的数成对出现。

证明：

$n>2$ 时，由性质 3，每一对互质的数之和为 $n$，有 $\dfrac{\varphi(n)}{2}$ 对，总和为$\displaystyle\frac{\varphi(n)\times n}{2}$。 注意： 若考虑到 $n=1$，可以归纳为 $$\sum_{k=1}^{n}k\times[k\perp n]=\frac{\varphi(n)\times n+[n=1]}{2}$$

• 【链接】欧拉函数性质

2\ [求欧拉函数]

• 【方法】

若n的唯一分解为p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}，则 \displaystyle\varphi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_k})=n\prod_{p_i\mid n}(1-\frac{1}{p_i}).

证明：n的所有因子均为绝对均匀分布，因此p_1筛去\displaystyle \frac{1}{p_1}的数，p_2从剩下的里再筛去\displaystyle \frac{1}{p_2}的数\cdots以此类推。

因此我们可以分解质疑数，每遇到一个素因子p，乘以(1-\displaystyle\frac{1}{p})，分级质因数复杂度O(\sqrt n).

• 【代码】

  int phi(int x) {
        int ans = x;
        for(int i = 2; i * i <= x; ++i) 
            if(!(x % i)) {
                ans -= ans / i;
                do x /= i; while(!(x % i));
            }
        if(n != 1) --ans;
        return ans;
  }

3\ [筛欧拉函数]

• 【方法】埃拉托斯特尼筛法

初始化所有 \varphi(i)=i，每当遇到素数 p 时，将其所有倍数乘以 1-\displaystyle\frac{1}{p}。

若遇到 \varphi(i)=i 的，则表明其未被更改过，为素数。

• 【代码】

  void seive(int n) {
        for(int i = 1; i <= n; ++i) phi[i] = i;
        for(int i = 2; i <= n; ++i)
            if(phi[i] == i)
                for(int j = i; j <= n; j += i)
                    phi[j] -= phi[j] / i;
  }

• 【方法】线性筛

欧拉函数的线性筛法基于一条重要性质。

欧拉函数是积性函数.

积性函数：若\forall n\perp m,f(nm)=f(n)\cdot f(m)，则称f(x)为积性函数。若\forall n,m均成立，则称为完全积性函数，欧拉函数不是完全积性函数。

证明：

\displaystyle\varphi(n)=n\prod_{p_i\mid n}(1-\frac{1}{p_i}),\varphi(m)=m\prod_{p_j\mid m}(1-\frac{1}{p_j})

又∵n\perp m，p_i\not =p_j，所以

\displaystyle \varphi(n) \cdot \varphi(m)=nm\prod_{p_i\mid n}(1-\frac{1}{p_i})\prod_{p_j\mid m}(1-\frac{1}{p_j})=nm\prod_{p_k\mid nm}(1-\frac{1}{p_k})=\varphi(nm).

同素数的线性筛法，我们考虑让每个数只被最小素因子筛出。

因此，我们仍需借助已有素数集合。

对于当前的 i，枚举 i 的 p_j 倍。