标签：phi 函数 int 质数 varphi times prod 欧拉

一、欧拉函数

定义

\([1,n]\) 中与 \(n\) 互质的数的个数，称为欧拉函数，记为 \(\varphi(n)\)。

• 互质的定义：对于正整数 \(a\) 和 \(b\)，若 \(gcd(a,b)=1\)，则 \(a\) 和 \(b\) 互质。

性质

1. 若 \(p\) 是质数，则 \(\varphi(p)=p-1\)。
   证：因为 \(p\) 是质数，所以因数只有 \(1\) 和 \(p\)。对于 \([2,p-1]\)，与 \(p\) 的公因数只能是 \(1\)；对于 \(1\)，\(gcd(1,p)=1\)；显然，\(gcd(p,p)=p\)。所以，\(\varphi(p)=p-1\)。
2. 若 \(p\) 是质数，则 \(\varphi(p^k)=(p-1)p^{k-1}\)。
   证：对于 \([1,p^k]\) 构成的数列，相当于以 \(p\) 个数作为一个单元：\(1...p...2p...3p......p^k\)，一共有 \(\frac{p^k}{p}=p^{k-1}\) 个这样的单元。每个单元中，除了类似 \(p,2p,3p,...,p^k\) 这样的数，其它数都与 \(p^k\) 互质。所以，\(\varphi(p^k)=(p-1)p^{k-1}\)。
3. 欧拉函数是积性函数，即满足 若 \(gcd(m,n)=1\)，则 \(\varphi(mn)=\varphi(m)\varphi(n)\)。

计算公式

由唯一分解定理：对于任意大于 \(1\) 的自然数 \(n\)，可以分解为一系列质数之积，即 \(n=\prod_{i=1}^S{p_i^{a_i}},~~~~p_i为质数,~a_i为p_i的个数\)。

\[\varphi(n)=\begin{cases} 1&,n==1\\ n\times \prod_{i=1}^S{\frac{p_i-1}{p_i}}&,n\ge2 \end{cases} \]

注：仅由 \(n\) 和质因数 \(p_i\) 决定，与质因数个数 \(a_i\) 无关。

证：

\[\begin{split} \varphi(n)&=\varphi(\prod_{i=1}^S{p_i^{a_i}})\\ &=\prod_{i=1}^S{\varphi(p_i^{a_i})}~~~~由性质3\\ &=\prod_{i=1}^S{(p_i-1)p_i^{a_i-1}}~~~~由性质2\\ &=\prod_{i=1}^S{p_i^{a_i}(1-\frac{1}{p_i})}\\ &=\prod_{i=1}^S{p_i^{a_i}}\times \prod_{i=1}^S{(1-\frac{1}{p_i})}\\ &=n\times \prod_{i=1}^S{\frac{p_i-1}{p_i}}~~~~由唯一分解定理 \end{split} \]

二、求解算法

试除法

找到 \(n\) 的所有质因子，与 \(n\) 一起累乘即为所求。

int phi(int n)
{
    int res = n;

    for (int i = 2; i * i <= n; ++i)
    {
        if (n % i == 0)    // i是n的质因子
        {
            res = res * (i - 1) / i;

            while (n % i == 0)    n /= i;
        }
    }
    
    if (n > 1)    res = res * (n - 1) / n;
    
    return res;
}

筛法

该算法可以求出 \([1,n]\) 内所有数的欧拉函数。

算法简析

该算法基于线性筛。

对于质数，若 \(i\) 是质数，则 \(phi[i]=i-1\)。

对于合数，在筛数时求欧拉函数。设当前枚举到 \(i\)，遍历已知的质数 \(p_j\) 来筛数。令 \(m=i\times p_j\)，则 \(phi[m]\) 为

• 若 \(p_j\) 整除 \(i\)，则 \(\varphi(m)=p_j\times\varphi(i)\)。
  证：因为 \(p_j\) 整除 \(i\)，所以 \(i\) 包含 \(p_j\) 的所有质因子。又因为 \(m=i\times p_j\)，所以 \(i\) 与 \(m\) 的质因子相同。

\[\begin{split} \varphi(m)&=m\times\prod_{k=1}^S{\frac{p_k-1}{p_k}}~~~~计算公式\\ &=p_j\times i\times\prod_{k=1}^S{\frac{p_k-1}{p_k}}\\ &=p_j\times\varphi(i) \end{split} \]

• 若 \(p_j\) 不能整除 \(i\)，则 \(\varphi(m)=(p_j-1)\times\varphi(i)\)。
  证：因为 \(p_j\) 不能整除 \(i\)，则 \(i\) 与 \(p_j\) 互质。由性质1和2，则 \(\varphi(m)=\varphi(i\times p_j)=\varphi(p_j)\times\varphi(i)=(p_j-1)\times\varphi(i)\)。

Code

const int MAX = 1e8 + 5;
bool vis[MAX];      // vis[i] -- i是否筛去 
int p[MAX], cnt;    // p[] -- 存储质数; cnt -- 统计质数个数
int phi[MAX];       // phi[i] -- i的欧拉函数

void get_phi(int n)
{
	phi[1] = 1;
	
	for (int i = 2; i <= n; ++i)
	{
		if (!vis[i])
		{
			p[cnt++] = i;
			phi[i] = i - 1;
		}
		
		for (int j = 0; i * p[j] <= n; ++j)
		{
			int m = i * p[j];
			vis[m] = true;
			
			if (i % p[j] == 0)
			{
				phi[m] = p[j] * phi[i];
				break;
			}
			else
				phi[m] = (p[j] - 1) * phi[i];
		}
	}
}

---

完

标签：phi,函数,int,质数,varphi,times,prod,欧拉
From： https://www.cnblogs.com/hoyd/p/18204586