欧拉函数

定义

欧拉函数(Euler’s totient function)，即 $\varphi(n)$，表示的是小于等于 $n$ 的数中与 $n$ 互质的数字个数，

例如 $\varphi(1)=1$。

性质

$\bullet 1.$ 欧拉函数是积性函数。

$\ \ $ 积性函数的意思是：如果有 $\gcd(a,b)=1$，那么则有 $\varphi(a)=\varphi(a) \times \varphi(b)$。

$\ \ $ 特别的，当 $n$ 为奇数时，$\varphi(2n)=\varphi(n)$。

$\bullet 2.$ 当 $n$ 为质数时，有 $\varphi(n)=n-1$。

$\bullet 3.$ $\forall n>1,1$~$N$ 中所有与 $n$ 互质的数的和为 $\frac{n\cdot \varphi(n)}{2}$

$\hspace{0.5em}$ 证明：

$\hspace{0.5em}$ 根据更相相减法，因为 $\gcd(n,x)=\gcd(n,n-x)$，所以予 $n$ 互质的数 $x,n-x$ 成对出现，平均值为 $\frac{n}{2}$，故和为 $\frac{n\cdot \varphi(n)}{2}$

$\bullet 4.$ 若 $p$ 为质数，则 $\varphi(p^k)=p^k-p^{k-1}$。

$\hspace{0.5em}$ 证明：

$\hspace{0.5em}$ 因为 $p$ 为质数，所以与 $p$ 不互质的数就只能为 $p$ 的倍数，共 $p^{k-1}$ 个。所以减去这些就是 $\varphi(n)$ 的值。

$\bullet 5.$ 若 $p$ 为质数，若 $p\mathrel{|}n$ 且 $p^2\mathrel{|}n$，则 $\varphi(n)=\varphi(\frac{n}{p})\cdot p$；若$p$为质数，若 $p\mathrel{|}n$ 且 $p^2\nmid n$，则 $\varphi(n)=\varphi(\frac{n}{p})\cdot(p-1)$

$\hspace{0.5em}$ 证明：

$\hspace{0.5em}$ 第一条：因为 $n$ 与 $\frac{n}{p}$ 的质因子相同，只是 $p$ 的指数不同。所以 $\frac{\varphi(n)}{\varphi(\frac{n}{p})}=p$，即可得原式。

$\hspace{0.5em}$ 第二条：根据性质一，即欧拉函数为积性函数，可得 $\varphi(n)=\varphi(\frac{n}{p})\cdot\varphi(p)$，因为 $p$ 为质数，由性质二可得原式。

$\bullet 6.$ $n=\sum\limits_{d\mathrel{|}n}^{}\varphi(d)$。

$\hspace{0.5em}$ 证明如下图：

用法

举个栗子:The Euler function

题意：求$\sum\limits_{i=a}^{b}\varphi(i)$

如果枚举必定 $TLE$。

方法一：

用埃氏筛，由欧拉函数的展开式 $\varphi(N)=N\cdot\prod\limits_{质数p\mid N}^{}(\frac{p-1}{p})$，

对于筛出的每个质数 $p$，将 $p$ 的倍数的欧拉函数值除以 $p$ 再乘 $p-1$ 即可。

时间复杂度 $O(N\log N)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
template<typename P>
inline void read(P &x){
   	P res=0,f=1;
   	char ch=getchar();
   	while(ch<'0' || ch>'9'){
   		if(ch=='-') f=-1;
   		ch=getchar();
   	}
   	while(ch>='0' && ch<='9'){
   		res=res*10+ch-'0';
   		ch=getchar();
	}
	x=res*f;
}
using namespace std;
const int N=3000005;
int a[N],b[N],tot=1,maxn;
int phi[N];
void initprime(int n){
	for(int i=2;i<=n;i++) phi[i]=(int)i;
	for(int i=2;i<=n;i++) if(phi[i]==(int)i)
		for(int j=i;j<=n;j+=i) phi[j]/=(int)i,phi[j]*=(int)(i-1);
	for(int i=1;i<=n;i++) phi[i]+=phi[i-1];
}
signed main(){
	auto solve=[&](){
		while(scanf("%d%d",&a[tot],&b[tot])!=EOF) maxn=max(maxn,b[tot]),tot++;
		initprime(maxn);
		for(int i=1;i<tot;i++) printf("%lld\n",phi[b[i]]-phi[a[i]-1]);
		return;
	};
	return 0;
}

方法二自己搜，不想写了。