欧拉函数

概念

定义 $\varphi (n)$ 为欧拉函数 其等于 1~n当中与n互质的数的个数 公式 $\varphi (N)=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})......\frac{1}{p_k}$ 其中 p 为质数

证明

利用 容斥原理 证明，将公式乘开可以看到： 1. 奇数$P_k$相减，偶数$p_k$相加，正是不考虑重叠部分，先减去再加回 2. 首先，每个数都可以拆成质因数p相乘，$\frac{N}{p}$ 意味着1~N中，p的倍数的个数，其余N都有p为约数，所以不是互质数，$N-\frac{N}{p}$ 就是去掉这些数，由于每个数都是p的相乘(或幂)，$\frac{N}{p}$ 可以表示N以内所有可能的数。 3. 容斥原理，先减去再加回可以算出剩余的数，即互质数的个数

欧拉函数计算

算法实现

给定数求欧拉函数

1. 分解质因数
2. 公式计算

int a;
cin >> a;
 
LL ans = a;
 
for(int i = 2; i <= a/i; i ++)
{
	int ans = a;
	if(a % i == 0)
	{
		ans = ans / i * (i - 1);  // 不能有1/i，所以公式变一下
		while(a % i == 0)
		{
			a /= i;
		}
	}
}
 
if(a > 1)
	ans = ans / a * (a - 1);
 
cout << ans << endl;
}

给定数范围求欧拉函数

1. 线性筛法找质数
2. 分类计算欧拉函数 有

   欧拉函数 2024-02-26 22.28.03.excalidraw

   ⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

   Text Elements

   i % p[j] = 0

   因为当p[j]是i的最小质因子时，有i*p[j]的质因子组成 和i的组成一样

   i % p[j] != 0

   因为当不等于0，p[j]不是i的质因子，i*p[j]就比i多一个质因子p[j]

   Link to original

for(int i = 2; i <= n; i ++)
{
	if(!st[i])
	{
		p[cnt ++] = i;
		phi[i] = i - 1;  //素数的欧拉函数是i-1
	}
 
	for(int j = 0; p[j] <= n / i; j ++)
	{
		st[i * p[j]] = true;
 
		if(i % p[j] == 0)
		{
			phi[i * p[j]] = p[j] * phi[i]; //上述分类
			break;
		}
 
		phi[i * p[j]] = (p[j] - 1) * phi[i];
}