欧拉函数
我们用$phi(n)$表示欧拉函数
定义:$phi(n)$表示对于整数$n$,小于等于$n$中与$n$互质的数的个数
性质
1.$phi(n)$为积性函数
证明:
此处证明需要用到下面计算方法1中的内容,建议先看后面再回过头来看这里
假设存在$p,q$,且$p*q=n$
将$n,p,q$进行质因数分解
$n=a_1^{p_1}a_2^{p_2}...a_k^{p_k}$
$p=a_1^{p_1}a_2^{p_2}...a_m^{p_m}$
$q=a_{m+1}^{p_{m+1}}a_{m+2}^{m+2}...a_k^{p_k}$
那么
$varphi left( nright) =nprod ^{k}{i=1}left( 1-dfrac {1}{p{i}}right)$
$varphi left( aright) =aprod ^{m}{i=1}left( 1-dfrac {1}{p{i}}right)$
$varphi left( bright) =bprod ^{k}{i=m+1}left( 1-dfrac {1}{p{i}}right)$
因为$n=a*b$
显然
$varphi left( nright) =varphi left( aright) varphi left( bright)$
这种方法也是常见的证明一个函数是积性函数的方法
2.$sum_{d|n}phi(d)=n$
3.$1$到$n$中与$n$互质的数的和为$n*dfrac{phi(n)}{2}(n>1)$
证明:若$gcd(n, i) = 1$,那么$gcd(n, n - i) = 1$
因此与$n$互质的数都是成对出现的。且每一对的和都为$n$
这样最终答案为$n * frac{phi(n)}{2}$
- $a^{phi(n)} equiv 1 pmod n$
:
计算方法
$sqrt(n)$计算单值欧拉函数
假设我们需要计算$phi(n)$
分情况讨论
1.当$n=1$时
很明显,答案为$1$
2.当$n$为质数时
根据素数的定义,答案为$n-1$
(仅有$n$与$n$不互质)
3.当$n$为合数时
我们已经知道了$n$为素数的情况
不妨对$n$进行质因数分解
设$n=a_1^{p_1}a_2^{p_2}...a_k^{p_k}$
假设$k=1$
那么$phi(p^k)=p^k-p^{k-1}$
证明:
考虑容斥,与一个数互素的数的个数就是这个数减去与它不互素的数的个数
因为$p$是素数,所以在$p^k$中与其不互素的数为$1p$,$2p$....$p^{k-1}*p$,有$p^{k-1}$个
得证
当$kneq 1$时
$$phi(n)$$
$$=varphi left( a^{p_{1}}{1}a^{p{2}ldots }{2}a^{Pk}{k}right)$$
$$=prod ^{k}{i=1}a^{P_i}-a^{P{i}-1}_{i}$$
$$=prod ^{k}{i=1}a^{Pi}{i}(1-dfrac {1}{p_{i}})$$
$$=n*prod ^{k}{i=1}(1-dfrac {1}{p{i}})$$
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1e7 + 10;
int p, ans = 1, N;
void GetPhi() {
for(int i = 2; i * i <= p; i++) {
if(p % i == 0) {
int now = i - 1; p /= i;
while(p % i == 0) now = now * i, p /= i;
ans = ans * now;
}
}
if(p != 1) ans *= (p - 1);
}
int main() {
cin >> p; N = p;
GetPhi();
cout << ans;
return 0;
}
线性筛
因为欧拉函数是积性函数
因此可以使用线性筛法
性质1
若$p$为素数,则$varphi left( pright) =p-1$
证明:
在$1-p$中,只有$(p,p)neq1$
性质2
若$i mod p neq 0$,且$p$为素数
则$varphi left( ipright) =varphi left( iright) varphi left( pright)$
$=varphi left( iast pright) =varphi left( iright) ast left( p-1right)$
这一步同时利用了性质1和欧拉函数的积性
性质3
若$i mod p = 0$,且$p$为素数,
则$varphi left( iast pright) =varphi left( iright) ast p$
证明:
没怎么看懂,丢一个链接
http://blog.csdn.net/Lytning/article/details/24432651
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 10;
void GetPhi(int N) {
static int phi[MAXN], vis[MAXN], prime[MAXN], tot = 0;
for(int i = 2; i <= N; i++) {
if(!vis[i]) prime[++tot] = i, phi[i] = i - 1;
for(int j = 1; j <= tot && i * prime[j] <= N; j++) {
vis[i * prime[j]] = 1;
if(!(i % prime[j])) {phi[i * prime[j]] = phi[i] * prime[j]; break;}
else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
while(cin >> N) cout << phi[N] << endl;
}
int main() {
GetPhi(100);
return 0;
}
例题
放几道水题
http://poj.org/problem?id=2407
http://poj.org/problem?id=2478
https://www.luogu.org/problemnew/show/P2158
参考资料
原文链接: https://www.cnblogs.com/zwfymqz/p/8215259.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/268498
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!