互质与欧拉函数学习笔记

发表于

互质与欧拉函数学习笔记

互质

定义：

​ $\forall a,b\in \N$ ，若 $gcd(a,b)=1$ ，则称 $a,b$ 互质。

积性函数

定义：

​ 如果 $a,b$ 互质时，有 $f(ab)=f(a)*f(b)$ ，那么称函数 $f$ 为积性函数。

性质：

​ 若 $f$ 为积性函数，且在算数基本定理中， $n=\prod\limits_{i=1}^m p_i^{c_i}$ ，则 $f(n)=\prod\limits_{i=1}^m f(p_i^{c_i})$ 。

欧拉函数

  • 定义：

​ $1\sim N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\varphi(N)$ 。

若在算数基本定理中， $N=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$ ，则： $\varphi(N)=N\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}\cdots\frac{p_m-1}{p_m}=N*\prod\limits_{质数p\mid N}(1-\frac{1}{p})$ 。

证明：

​ 设 $p$ 是 $N$ 的质因子， $1\sim N$ 中 $p$ 的倍数共有 $N/p$ 个。同理，若 $q$ 也是 $N$ 的质因数，则 $1\sim N$ 中 $q$ 的倍数有 $N/q$ 个。若我们将这 $N/p+N/q$ 个数去掉，那么 $p*q$ 的倍数被排除了两次，需要加回来一个。因此，根据容斥原理， $1\sim N$ 中不与 $N$ 含公共质因子 $p$ 或 $q$ 的数的个数为：

​ $N-\frac{N}{p}-\frac{N}{q}+\frac{N}{pq}=N(1-\frac{1}{p})(1-\frac{1}{q})$

​ 类似的，我们对于 $N$ 的全部质因子使用容斥原理，即可得到 $\varphi(N)$ 。

  • 性质
    1. $\forall n>1,1\sim n$ 中与 $n$ 互质的数之和为 $n*\varphi(n)/2$ 。
    2. 若 $a,b$ 互质，则 $\varphi(ab)=\varphi(a)\varphi(b)$ 。
    3. 设 $p$ 为质数，若 $p\mid n$ 且 $p^2\mid n$ ，则 $\varphi(n)=\varphi(n/p)*p$ 。
    4. 设 $p$ 为质数，若 $p\mid n$ 且 $p^2\not|n$ ，则 $\varphi(n)=\varphi(n/p)*(p-1)$ 。
    5. $\sum\limits_{d|n}\varphi(d)=n$ 。

证明：

​ 因为 $gcd(n,x)=gcd(n,n-x)$ ，所以与 $n$ 不互质的数 $x,n-x$ 成对出现，平均值为 $n/2$ 。因此，与 $n$ 互质的数的平均值也是 $n/2$ ，性质 $1$ 成立。

​ 根据欧拉函数的计算式，因为 $gcd(a,b)=1$ ，所以它们没有除了 $1$ 以外的公约数，计算时不会重复出现 $(1-\frac{1}{p})$ ，性质 $2$ 成立。

​ 若 $p\mid n$ 且 $p^2\mid n$ ，则 $n,n/p$ 包含相同的质因子，按照欧拉函数的计算公式，两者相除商为 $p$ ，性质 $3$ 成立。

​ 若 $p\mid n$ 且 $p^2\not|n$ ，则 $gcd(n,n/p)=1$ ，由 $\varphi$ 是积性函数得 $\varphi(n)=\varphi(n/p)*\varphi(p)$ 。其中 $\varphi(p)=p-1$ ，性质 $4$ 成立。

​ 设 $f(n)=\sum\limits_{d|n}\varphi(d)$ 。用乘法分配率展开比较，再利用 $\varphi$ 是积性函数，得到：若 $gcd(n,m)=1$ ，则 $f(nm)=\sum\limits_{d|nm}\varphi(d)=(\sum\limits_{d|n}\varphi(d))(\sum\limits_{d|m}\varphi(d))=f(n)f(m)$ 。即 $f$ 是积性函数，对于单个质因子， $f(p^m)=\sum\limits_{d|p^m}\varphi(d)=\varphi(1)+\varphi(p)+\varphi(p^2)+\cdots+\varphi(p^m)$ 是一个等比数列求和再加 $1$ ，结果为 $p^m$ 。所以 $f(n)=\prod\limits_{i=1}^m f(p_i^{c_i})=\prod\limits_{i=1}^m p_i^{c_i}=n$ ，性质 $5$ 成立。

例题

题面

Luogu P2158 [SDOI2008]仪仗队

Solution

分析题目可以发现，除了 $(1,0)$ ， $(0,1)$ 和 $(1,1)$ 三个点之外，一个钉子 $(x,y)$ 能被看到，当且仅当 $gcd(x,y)=1$ 时成立。

由于能看到的钉子明显是关于 $y=x$ 这条直线对称的，所以我们只需要求其中一半即可。对于该坐标系的右下方可以看到的钉子，满足对于每个 $2\leq x\leq N$ 都有 $1\leq y<x,gcd(x,y)=1$ 。这样的 $y$ 的数量恰好就是 $\varphi(x)$ 。

综上所述，本题的答案就是 $3+2*\sum\limits_{i=2}^N\varphi(i)$ 。我们要做的就是求出 $2\sim N$ 中每个数的欧拉函数。

Code

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
template<class T>void read(T &x)
{
 	x=0;char k=getchar();int f=1;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=x*10+k-'0';
	x*=f;
}
int n,ans;
int prime[40005],tot,phi[40005];
bool is_not_pr[40005];
inline void prepare()
{
	phi[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!is_not_pr[i])
		{
			prime[++tot]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=tot&&i*prime[j]<n;j++)
		{
			is_not_pr[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else phi[i*prime[j]]=phi[i]*phi[prime[j]];
		}
	}
}
int main()
{
	read(n);
	if(n==1) printf("0");
	else
	{
		prepare();
		for(int i=2;i<n;i++) ans+=phi[i];
		printf("%d\n",ans*2+3);
	}
	return 0;
}

总结

这一部分的题要善于问题转化，将问题化简为可做的模式，同时它的拓展——欧拉反演也是比较重要的一类题，要抽时间去看一下。