概念
$若a,b\in\Z,\gcd(a,b)=1,则称a与b\color{Blue}互质\\\color{black}对于n\in\Z,将区间[1,n]中与n互质的个数称为\color{Blue}{欧拉函数},记作\varphi(n)$
欧拉函数
证明：
若一个数质因数与n的质因数都不相同，则这个数和n互质，因此我们只需要考虑不是n的质因数的质数可以构成多少$[1,n]$内的正整数即可。
$\because 对于n的质因数p_i,都在[1,n]内有n\cdot \dfrac{1}{p_i}个数与n有共同的质因数p_i\\\therefore 对于质因数p_i,都在[1,n]内有n\cdot (1-\dfrac{1}{p_i})个数不是质因数p_i的倍数\\\therefore 不是n任何一个质因数倍数的数在[1,n]内有n\cdot\prod\limits_{i=1}^{m}(1-\dfrac{1}{p_i})个\\\therefore \varphi(n)=n\cdot\prod\limits_{i=1}^{m}(1-\dfrac{1}{p_i})$
1 |
|
- 下文中的所有 $p_i$ 都表示质因数，$p$表示质数
简单性质
证明：
$\because n=p^k,p为质数\\\therefore n的质因数只有p\\\therefore 若\gcd(a,n)\ne1\Leftrightarrow \forall s\in\Z,s\cdot p\leq p^k,a=sp\\\therefore s\leq p^{k-1}\\\therefore 有p^{k-1}个 a不与n互质\\\therefore ,\varphi(n)=p^k-p^{k-1}=p^{k-1}(p-1)$
证明：
$\because \gcd(n,m)=1,所以n与m的质因数集合无交集\\\therefore 可将n的质因数集合表示为P=\{p_i\mid \, 1\leq i\leq \alpha\},m的质因数集合表示为Q=\{p_i\mid \, \alpha+1\leq i\leq \beta\}\\\therefore nm的质因数集合可以表示为P\cup Q ,即\{p_i\mid \, 1\leq i\leq \beta \}\\\therefore \varphi(n)\cdot \varphi(m)=n\cdot m\cdot \prod\limits_{i=1}^{\alpha}(1-\dfrac{1}{p_i})\cdot \prod\limits_{i=\alpha+1}^{\beta}(1-\dfrac{1}{p_i})\\\qquad \qquad \qquad \, \, =nm\cdot\prod\limits_{i=1}^{\beta}(1-\dfrac{1}{p_i})\\\qquad \qquad \qquad \, \, =\varphi(nm)$
证明：
$考虑p\mid\varphi(n)\\\therefore \exist s,k\in\Z,n=p^k\cdot s\\\therefore \gcd(\dfrac{n}{p^k},p^k\cdot p)=1\\\because 欧拉函数是积性函数\\\therefore \varphi(n\cdot p)=\varphi(\dfrac{n}{p^k})\cdot\varphi(p^{k+1})\\\quad =\dfrac{n}{p^k}\cdot\dfrac{\prod\limits_{i=1}^{m}(1-\dfrac{1}{p_i})}{(1-\dfrac{1}{p})}\cdot p^k(p-1)\\\quad =n\cdot \dfrac{1}{p^k}\cdot p^k\cdot \prod\limits_{i=1}^{m}(1-\dfrac{1}{p_i})\cdot \dfrac{p}{p-1}\cdot (p-1)\\\quad =n\cdot \prod\limits_{i=1}^{m}(1-\dfrac{1}{p_i})\cdot p\\\quad =\varphi(n)\cdot p\\考虑p \nmid n\\\because p\nmid n,p为质数\\\therefore \gcd(p,n)=1\\\therefore \varphi(n\cdot p)=\varphi(n)\cdot \varphi(p)$
证明：
$考虑g\in \Z,g\mid a,g\mid b\\\because \exist s,k\in\Z a=s\cdot g,b=k\cdot g\\\therefore a-b=g(s-k)\\\therefore g\mid (a-b)\\\therefore 所以(a-b)的因数集与a与b的公因数集完全相同\\\therefore 若 a>b，gcd(a,b)=gcd(a,a-b)=gcd(b,a-b)\\\therefore 当\gcd(n,m)=1,都有\gcd(n,n-m)=1\\\therefore 与n互质的数是成对出现的\\\therefore \forall n>2，2\mid \varphi(n)\\对于n<2的情况请读者自行考虑验证$
证明：
$\because 引用性质6证明中的结论，若m与n互质，必有n-m也与n互质\\\therefore m+(n-m)=n\\\because n中与n互质的数对(m,n-m)有\varphi(n)\cdot \dfrac{1}{2}对\\\therefore [1,n]中与
n互质的数的和为：\\\quad (m+(n-m))\cdot \dfrac{\varphi(n)}{2}\\\quad =n\cdot \dfrac{\varphi(n)}{2}$
证明：
$考虑f(n)=\sum_{d\mid n}\varphi(n),试证明当\gcd(n,m)=1时，f(n\cdot m)=f(n)\cdot f(m)\\f(n)\cdot f(m)=\sum_{i\mid n}\varphi(i)\cdot \sum_{j\mid m}\varphi(j)\\\qquad\qquad\quad\,\, =\varphi(i_1)\cdot \varphi(j_1)+\varphi(i_1)\cdot \varphi(j_2)+\varphi(i_1)\cdot \varphi(j_3)\cdots \varphi(i_1)\cdot \varphi(j_m)+\varphi(i_2)\cdot \varphi(j_1)+\varphi(i_2)\cdot \varphi(j_2)\cdots \varphi(i_n)\cdot \varphi(j_m)\\\qquad\qquad\quad\,\,= \varphi(i_1\cdot j_1)+\varphi(i_1\cdot j_2)\cdots+\varphi(i_n\cdot j_m)\\\because gcd(n,m)=1\\\therefore 可以得到，i_1\cdot i_2\cdots i_n\cdot j_m构成了n\cdot m的所有因数\\\therefore \gcd(n,m)=1，f(nm)=f(n)\cdot f(m)\\\,\\\because p为质数，有f(p^k)=\varphi(1)+\varphi(p)+\varphi(p^2)\cdots +\varphi(p^k)=1+(p-1)+(p^2-p)\cdots+(p^k-p^{k-1})=p^k\\\because 任意整数n=p_1^{c_1}\cdot p_2^{c_2}\cdots p_m^{c_m}\\\therefore \forall n\in \Z,f(n)=f(p_1^{c_1}\cdot p_2^{c_2}\cdots p_m^{c_m})=f(p_1^{c_1})\cdot f(p_2^{c_2})\cdots f(p_m^{c_m})=p_1^{c_1}\cdot p_2^{c_2}\cdots p_m^{c_m}=n\\\therefore 结论成立$
证明：
$考虑一个模m的互质剩余系\{x_1,x_2,x_3\cdots x_{\varphi(m)}\}，其中x小于m，且都与m互质。\\\because \gcd(x_k,m)=1，\gcd(a,m)=1\\\therefore \gcd(a\cdot x_k,m)=1，且ax_i两两互质。\~\\此时考虑证明 ax_i\not\equiv ax_j\pmod m//$
因此有$\{ax_1,ax_2.ax_3\cdots ax_m\}$也是互质同余系，因此利用同模数同余式的合并性质，有
证毕
区间内的欧拉函数求值
由于欧拉函数可以从质因数得到，我们不难想到可以利用埃氏筛和线性筛两种方法求出$[1,n]$内的欧拉函数值。
- 埃氏筛
在埃氏筛中，每一个数都会被它的质因数筛一遍，我们可以利用这点在埃氏筛中完成欧拉函数求值
我们甚至可以直接用 $\varphi$ 数组代替标记数组！
1 |
|
- 线性筛
另外我们可以发现 $\mathbf{性质5}$ 的结论仿佛就是为线性筛量身定制的，因此我们也可以通过线性筛使用线性复杂度来求出$[1,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
using namespace std;
int n;
double phi[1000010]={0};
int prime[100010],tot=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++) phi[i]=i;
for(int i=2;i<=n;i++)
{
if(phi[i]==i)
{
prime[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot&&i*prime[j]<=n;j++)
{
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else
{
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
for(int i=1;i<=n;i++) cout<<phi[i]<<endl;
return 0;
}
1 |
|