【7】欧拉函数学习笔记
w9095
·
·
算法·理论
前言
从 这篇博客 中分离出来的。
欧拉函数是一个常用且好用的数论函数，有许多神奇的性质。
欧拉函数
欧拉函数：对正整数 n ，欧拉函数是小于 n 的正整数中与 n 互质的数的数目，记作 \varphi(n) 。
欧拉函数的性质：
1$：$\varphi(1)=1
$3$：$\varphi(p^k)=p^k-p^{k-1}=(p-1)*p^{k-1}
4$：欧拉函数是**积性函数**，若 $m,n$ 互质则有 $\varphi(m\times n)=\varphi(m)\times \varphi(n)
$$\varphi(n)=n\times\prod_{i=1}^r(1-{\frac 1 {p_{i}}})$$
对于性质 $5$，我们可以感性理解。就相当于枚举 $n$ 的每个质因数，把小于 $n$ 且有这个因数的数除去，剩下的就是互质的数。
依据性质 $5$，我们可以得出单个求欧拉函数的算法。
对 $n$ 进行质因数分解，按照性质 $5$ 的公式进行计算。实际上就是把式子用代码实现了而已。时间复杂度 $O(\sqrt{n})$。
```cpp
long long phi(long long x)
{
long long ans=x;
for(long long i=2;i*i<=x;i++)
if(x%i==0)
{
ans=ans/i*(i-1);
while(x%i==0)x/=i;
}
if(x!=1)ans=ans/x*(x-1);
return ans;
}
```
我们可以在线性筛的过程中，线性预处理出 $1\sim n$ 个数的欧拉函数值。
对于性质 $4$，我们知道欧拉函数是积性函数，所以如果我们知道了 $\varphi(n)$ 的值，并知道一个 $n$ 中不存在的质数 $m$，这两个数就一定互质，就可以用 $\varphi(n)\times \varphi(m)$ 得到 $mn$ 的欧拉函数值。
根据性质 $2$，$\varphi(mn)=\varphi(n)\times(m-1)$。
在线性筛的过程中，我们有时确实会出现这种情况。当我们由点 $n$ 乘以其中不存在的质因数 $m$ 筛掉点 $mn$ 时，可以顺便求出 $\varphi(mn)$。但如果不互质，也就是点 $n$ 中存在质因数 $m$，我们直接将 $\varphi(n)$ 乘以 $m$ 即可得到 $\varphi(mn)$。根据性质 $5$，这个 $m$ 并没有导致出现新的质因数，所以乘积式的后一项累乘式结果不变，但是前面的 $n$ 变成了 $mn$，所以总体就乘以了 $m$。这种情况下，线性筛对点 $n$ 的扩展也刚好结束。
由于我们从小到大枚举，且递推式中没有出现后面的值，每一次都知道 $\varphi(n)$，满足递推的条件。时间复杂度 $O(n)$，均摊 $O(1)$。
```cpp
void linear(long long n)
{
a[1]=1;phi[1]=1;
for(long long i=2;i<=n;i++)
{
if(!a[i])pri[++cnt]=i,phi[i]=i-1;
for(long long j=1;j<=cnt&&i*pri[j]<=n;j++)
{
a[i*pri[j]]=1;
phi[i*pri[j]]=phi[i]*(pri[j]-1);
if(i%pri[j]==0)
{
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
}
}
}
```
### 重要性质
$$\sum_{d\mid n}\varphi(d)=n$$
感性理解，记忆即可，证明我不会。
这个性质常用来简化式子，优化复杂度。多用于处理 $\gcd$ 相关问题。例如下面这个式子：
$$\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)$$
求解这个式子，时间复杂度为 $O(n^2)$。
套用性质，得到这个式子：
$$\sum_{i=1}^n\sum_{j=1}^n\sum_{d\mid gcd(i,j)}\varphi(d)$$
将含 $\gcd$ 的式子按照 $\gcd$ 的性质（若 $d\mid\gcd(x,y)$，则 $d\mid x,d\mid y$）展开，得到：
$$\sum_{i=1}^n\sum_{j=1}^n\sum_{d\mid i,d\mid j}\varphi(d)$$
交换枚举顺序，我们先枚举 $d$，问题就变成了求 $d$ 等于某值时满足条件的 $i,j$ 的数量，用这个数量乘以 $\varphi(d)$ 就能求出这一部分的答案，最后累加即可。$n$ 以内有 $\lfloor\frac{n}{d}\rfloor$ 个数满足 $ d\mid i$，因为每 $d$ 个就有一个数满足条件。$j$ 的数量也是同理。根据乘法原理，总共有 $\lfloor\frac{n}{d}\rfloor^{2}$ 个数满足条件，所以得到：
$$\sum_{d=1}^n\varphi(d)\lfloor\frac{n}{d}\rfloor^{2}$$
时间复杂度为 $O(n)$。
### 例题
例题 $1$ ：
[UVA10179 Irreducable Basic Fractions](https://www.luogu.com.cn/problem/UVA10179)
根据约分的定义，我们发现分母为 $n$ 的不可约简单分数的数量就是与 $n$ 互质的小于 $n$ 的数的数量。这样就转化为了欧拉函数模板题，每次询问单独求解即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,a;
bool flag=0;
int eulerfun(int a)
{
int ans=a;
for(int i=2;i*i<=a;i++)
if(a%i==0)
{
ans=ans/i*(i-1);
while(a%i==0)
a/=i;
}
if(a!=1)ans=ans/a*(a-1);
return ans;
}
int main()
{
while(scanf("%d",&a)!=0)
{
if(a==0)return 0;
if(flag)printf("%d\n",eulerfun(a));
else printf("%d\n",eulerfun(a));
flag=1;
}
return 0;
}
```
例题 $2$ ：
[P2158 [SDOI2008] 仪仗队](https://www.luogu.com.cn/problem/P2158)
由我们生活中的经验或者看图说话，所以如果一个人在点 $(x,y)$，如果 $\gcd(x,y)=1$，他就能被看到。
我们先假定 $x\lt y$，则问题转化为了小于 $n$ 的正整数中与 $n$ 互质的数的数量，这就是欧拉函数的定义。我们线性处理出 $1\sim n$ 的欧拉函数值，然后求和，就得出了这一部分的答案。
由于 $x$ 可能大于 $y$，我们也需要考虑。思考之后我们发现只需要把上一部分中的 $x,y$ 互换即可。上一部分中每一个满足条件的数值都对应这个部分中的一个数值，答案需要乘以 $2$。
当然，也需要考虑 $x=y$ 的情况。很显然，这种情况下只有 $(1,1)$ 会被看到，答案还需要加 $1$。
注意特判 $n=1$ 的情况。
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,pri[1000001],f[1000001];
bool a[1000001];
int linear(bool a[],int pri[],int n)
{
int cnt=0;
a[1]=1;f[1]=1;
for(int i=2;i<=n;i++)
{
if(!a[i])
{
pri[cnt++]=i;
f[i]=i-1;
}
for(int j=0;pri[j]<=n/i;j++)
{
a[i*pri[j]]=1;
if(i%pri[j]==0)
{
f[i*pri[j]]=f[i]*pri[j];
break;
}
f[i*pri[j]]=f[i]*(pri[j]-1);
}
}
return cnt;
}
int main()
{
long long ans=0;
scanf("%d",&n);
if(n==1)
{
printf("0");
return 0;
}
linear(a,pri,n-1);
for(int i=1;i<=n-1;i++)
ans+=f[i];
printf("%lld",ans*2+1);
return 0;
}
```
例题 $3$ ：
[P2398 GCD SUM](https://www.luogu.com.cn/problem/P2398)
同重要性质部分，不多赘述。
```cpp
#include <bits/stdc++.h>
using namespace std;
long long n,pri[100000001],f[100000001];
bool a[100000001];
int linear(bool a[],long long pri[],long long n)
{
int cnt=0;
a[1]=1;f[1]=1;
for(int i=2;i<=n;i++)
{
if(!a[i])
{
pri[cnt++]=i;
f[i]=i-1;
}
for(int j=0;pri[j]<=n/i;j++)
{
a[i*pri[j]]=1;
if(i%pri[j]==0)
{
f[i*pri[j]]=f[i]*pri[j];
break;
}
f[i*pri[j]]=f[i]*(pri[j]-1);
}
}
return cnt;
}
int main()
{
long long ans=0;
scanf("%lld",&n);
linear(a,pri,n);
for(int i=1;i<=n;i++)
ans+=(f[i]*(n/i)*(n/i));
printf("%lld",ans);
return 0;
}
```
例题 $4$ ：
[P2303 [SDOI2012] Longge 的问题](https://www.luogu.com.cn/problem/P2303)
很套路的进行转化，如下：
$$\sum_{i=1}^{n}\gcd(i,n)$$
套用重要性质，得到这个式子：
$$\sum_{i=1}^{n}\sum_{d\mid \gcd(i,n)}\varphi(d)$$
将含 $\gcd$ 的式子按照 $\gcd$ 的性质（若 $d\mid\gcd(x,y)$，则 $d\mid x,d\mid y$）展开，得到：
$$\sum_{i=1}^{n}\sum_{d\mid i,d\mid n}\varphi(d)$$
交换枚举顺序，我们先枚举 $d$，问题就变成了求 $d$ 等于某值时满足条件的 $i$ 的数量，用这个数量乘以 $\varphi(d)$ 就能求出这一部分的答案，最后累加即可。$n$ 以内有 $\lfloor\frac{n}{d}\rfloor$ 个数满足 $ d\mid i$，因为每 $d$ 个就有一个数满足条件。由于还有额外条件 $d\mid n$，所以我们把这个条件放在外层，得到：
$$\sum_{d\mid n}\varphi(d)\lfloor\frac{n}{d}\rfloor$$
我们可以在枚举因数的同时满足 $d\mid n$ 的条件，只需要枚举 $\sqrt{n}$ 之内的数。如果 $\frac{n}{d}$ 不等于 $d$，那么就再计算一次 $\frac{n}{d}$ 的情况。由于 $d$ 的范围很大，不能线性筛，所以每次单独计算欧拉函数值。时间复杂度为 $O(\text{因数个数}\times \sqrt{n})$。
```cpp
#include <bits/stdc++.h>
using namespace std;
long long n,ans=0;
long long phi(long long x)
{
long long ans=x;
for(long long i=2;i*i<=x;i++)
if(x%i==0)
{
ans=ans/i*(i-1);
while(x%i==0)x/=i;
}
if(x!=1)ans=ans/x*(x-1);
return ans;
}
int main()
{
scanf("%lld",&n);
for(long long i=1;i*i<=n;i++)
if(n%i==0)
{
ans+=phi(i)*(n/i);
if(n/i!=i)ans+=phi(n/i)*(n/(n/i));
}
printf("%lld\n",ans);
return 0;
}
```
例题 $5$ ：
[P1447 [NOI2010] 能量采集](https://www.luogu.com.cn/problem/P1447)
由我们生活中的经验或者看图说话，我们得到答案为这个式子：
$$2\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)-mn$$
非常套路的进行转化，套用重要性质，得到这个式子：
$$2\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d\mid \gcd(i,j)}\varphi(d)-mn$$
将含 $\gcd$ 的式子按照 $\gcd$ 的性质（若 $d\mid\gcd(x,y)$，则 $d\mid x,d\mid y$）展开，得到：
$$2\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d\mid i,d\mid j}\varphi(d)-mn$$
交换枚举顺序，我们先枚举 $d$，问题就变成了求 $d$ 等于某值时满足条件的 $i,j$ 的数量，用这个数量乘以 $\varphi(d)$ 就能求出这一部分的答案，最后累加即可。$n$ 以内有 $\lfloor\frac{n}{d}\rfloor$ 个数满足 $ d\mid i$，因为每 $d$ 个就有一个数满足条件。$j$ 的数量也是同理，有 $\lfloor\frac{m}{d}\rfloor$ 个。根据乘法原理，总共有 $\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$ 个数满足条件。注意这里不需要枚举大于 $m,n$ 中任意一值的部分，因为向下取整，这一部分必定为 $0$，所以得到：
$$=2\sum_{d=1}^{\min(n,m)}\varphi(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor-mn$$
```cpp
#include <bits/stdc++.h>
using namespace std;
long long n,m,pri[1000010],phi[1000010],cnt,ans;
bool a[1000010];
void linear(long long n)
{
a[1]=1;phi[1]=1;
for(long long i=2;i<=n;i++)
{
if(!a[i])pri[++cnt]=i,phi[i]=i-1;
for(long long j=1;j<=cnt&&i*pri[j]<=n;j++)
{
a[i*pri[j]]=1;
phi[i*pri[j]]=phi[i]*(pri[j]-1);
if(i%pri[j]==0)
{
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
}
}
}
int main()
{
scanf("%lld%lld",&n,&m);
linear(max(n,m));
for(int i=1;i<=min(n,m);i++)ans+=phi[i]*(n/i)*(m/i);
printf("%lld\n",ans*2-m*n);
return 0;
}
```
### 后记
熬到半夜准备打CF，结果一看时间是昨天，一气之下写的博客。