A Huster

0%

euler

Posted on Edited on Valine:

euler函数

euler函数是表示从1~n中与n互质的个数，互质的定义简单提一下，$gcd(a,b)=1$。

那么如何求一个数的euler函数？

我们可以将每个数与n求gcd一下，如果gcd为1，则贡献加1，时间复杂度为 $O(n logn)$，极其优秀（雾）

那么来思考更加优秀的算法（为什么一定要求euler函数($\varphi(n)$函数)呢QAQ）

引论

在算法基本定理中, $N = p1^{c1} p2^{c2} p3^{c3} …$ ,其中pi为质因数，那么：

简单证明：

设p是N的质因子，那么显然p的倍数与N不互质，这些数分别是$p1,p2…p*N/p$，

显然有N/p个，那么我们可以减去这N/p个。设q是N的质因子，那么同理，q的倍数的个数有N/q个，那么在这N/p和N/q个当中有同时是p和q的倍数的，而我们多减了一次，我们容斥一下可以得到：

那么推广到全部即可；

实现

我们可以枚举其质因数，不用素数筛，当中我们可以直接用自然数筛，将N中所有的该数倍数筛掉，那么之后的合数必然是之前质因数的组合乘积，但是我们已经筛掉，所以不可能筛到合数，并且我们只用筛到$\sqrt{n}$即可，这个证明较简单，不再赘述.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
#include<cmath>
using namespace std;
int main(){
	int n,lim,ans;
	scanf("%d",&n);
	lim=sqrt(n),ans=n;
	for(int i=2;i<=lim;i++)
		if(!(n%i)){
			ans=ans/i*(i-1);
			while(!(n%i)) n/=i;
		}
	if(n>1) ans=ans/n*(n-1);//质因数大于sqrt(n) 
}

性质

1.如果n>1，1~n中与n互质的数的和为$n*\varphi(n)/2$

简单证明：

根据更相减损术可得，$gcd(a,b)=gcd(a,a-b)$，那么与n互质的数成对出现，则平均数为n/2，那么易得到结论；

2.如果a,b互质,$\varphi(ab)=\varphi(a)\varphi(b)$

简单证明：

根据euler函数的计算公式可得：

==定义：满足性质2的函数为积性函数==

3.如果$f(n)$为积性函数，$n=\prod_{i=1}^{m}p_{i}^{c_{i}}$，那么$f(n)=\prod_{i=1}^{m}f(p_i^{c_{i}})$

简单证明：

类比积性函数的定义和定义式可以得到

4.设p为质数,p|n且$p^{2}|n$,那么$\varphi(n)=\varphi(n/p)*p$

简单证明:

这个就很好证了,显然 $p$ 和 $n/p$ 的质因数相同,那么定义式中只有N是不同的,那么拆开再合并定义式就可以得到结论;

5.设p为质数,p|n但$p^{2}\not\mid n$,那么$\varphi(n)=\varphi(n/p)*(p-1)$

简单证明:

显然,p与n/p互质,那么根据积性函数$\varphi(n)=\varphi(n/p)*\varphi(p)$,当中$\varphi(p)=p-1$(因为p是质数),那么结论显然;

==以上性质4,5可以用来线性求euler函数,在后面会提到==

6.$\sum_{d|n}\varphi(d)=n$

证明忽略(雾

euler函数的线性筛法

如果要求1~n的euler函数,那么如何求解?

暴力解法,对每一个数进行求解,那么可以得到一个$O(n\sqrt{n})$的算法;

如何更优?

运用性质4,5即可,在素数筛的过程中进行性质4,5的判断,然后统计;

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define maxn 100008
using namespace std;
int n,prim[maxn],vis[maxn],euler[maxn],m;
int main(){
	scanf("%d",&n);
	for(int i=2;i<=n;i++){
		if(!vis[i]){
			vis[i]=i;prim[++m]=i;
			euler[i]=i-1;//这个很好理解 
		}
		for(int j=1;j<=m;j++){
			if(prim[j]>vis[i]||prim[j]*i>n) break;
			vis[prim[j]*i]=prim[j];
			//素数筛 
			euler[prim[j]*i]=euler[prim[j]]*(i%prim[j]?(prim[j]-1):(prim[j]));
			//性质4,5的判断 
		}
	}
	return 0;
}

欧拉定理

简述:

证明略(不会(雾))

拓展欧拉定理

简述;

$gcd(a,n)=1,则a^{b}\equiv a^{b\% \varphi(n)}(mod n)$

简单证明:

设$b=p*\varphi(n)+r$,那么$r= b(mod \varphi(n))$,由欧拉定理可得:

扩展欧拉定理

​

本站访问次数：