欧拉函数 & 欧拉定理 学习笔记
Foreverxxx
·
2022-05-03 08:41:31
·
个人记录
欧拉函数
定义
欧拉函数 \varphi(x) 表示小于等于 x 的数中，与 x 互质 的数的个数。
通式
\\&=x \times \prod_{i=1}^n(1-\frac{1}{p_i})
\end{aligned}
其中 p_i 表示 x 的质因子，n 表示 x 的质因子的个数。
性质
$2.$ 如果 $x = 2 \times n$ （$n$ 为奇数），则 $\varphi(x) = \varphi(n)$，即在 $n$ 为奇数的时候，$\varphi(2n)=\varphi(n)$，毕竟此时 $2n$ 的质因数比 $n$ 只多了一个 $2$，由上面一式可以化得：
$\begin{aligned} \varphi(2n)&=2 \times n \times (1-\frac{1}{p_1}) \times (1-\frac{1}{p_2}) \times \cdots \times (1-\frac{1}{p_k}) \times (1-\frac{1}{2})\\
&=n \times (1-\frac{1}{p_1}) \times (1-\frac{1}{p_2}) \times \cdots \times (1-\frac{1}{p_k})\\
&=\varphi(n)
\end{aligned}
$\begin{aligned}
\varphi(x^k)&= x^k \times (1- \frac{1}{x})
\\&=x^k \times \frac{x-1}{x}
\\&=x^{k-1} \times (x-1)
\\&=x^k - x^{k-1}
\end{aligned}
> 积性函数，即对于函数 $f(x)$ 以及任意两个互质的数 $m,n$，满足 $f(mn)=f(m) \times f(n)$。
这也很好证明，柿子就不用写了（其实就是懒），毕竟 $m,n$ 的质数都不相同。
$5.$ 当 $x > 2$ 时，$\varphi(x)$ 为偶数。
因为由更相减损术 $\gcd(n,x) = \gcd(n,n-x)$ 可知，与 $n$ 互质的数都是成对出现的。
$6.$ 在小于 $n$ 的数中，与 $n$ 互质的数的总和为 $\varphi(n) \times \frac{n}{2}$，很好的一个结论。
$7.$ $n=\sum_{d|n}φ(d)$，即 $n$ 的因数（包括 $1$ 以及它自己）的欧拉函数之和等于 $n$。
附上来自 Morning_Glory 的证明：
### 线性求欧拉函数
方法和质数筛差不多，况且这种线性筛时间复杂度 $O(n)$ 级别，不仅算出了 $\varphi(1) \dots \varphi(n)$ ，并且筛出了质数。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+10;
int n;
int prime[maxn],cnt=0;
int phi[maxn];
void init(int n){
phi[1]=1;
for(register int i=2;i<=n;i++){
if(!prime[i]){
prime[++cnt]=i;
phi[i]=i-1;
}
for(register int j=1;j<=cnt&&i*prime[j]<=n;j++){
prime[prime[j]*i]=1;//标记这个数不是质数
if(i%prime[j]==0){
//通过积性函数的性质，根据prime[j+1]可以推导得出
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
int main(){
cin>>n;
init(n);
for(register int i=1;i<=n;i++){
cout<<phi[i]<<" ";
}
return 0;
}
```
### 对一个数求欧拉函数
根据欧拉函数的公式 $\varphi(x)=x \times (1-\frac{1}{p_1}) \times (1-\frac{1}{p_2}) \cdots \times (1-\frac{1}{p_n})$，我们只需要将 $1-\frac{1}{p}$ 转化为 $\frac{p-1}{p}$，然后根据公式枚举出质因数计算即可，时间复杂度 $O(\sqrt{n})$。
```cpp
#include<bits/stdc++.h>
using namespace std;
int calc(int n){
int ans=n;
for(register int i=2;i*i<=n;i++){
if(n%i==0){
ans=ans/i*(i-1);
//将1-1/p转化为 (p-1)/p
while(n%i==0) n/=i;
}
}
if(n>1) ans=ans/n*(n-1);
//最终判断n循环完后是否为质数
return ans;
}
int main(){
int n; cin>>n;
cout<<calc(n);
return 0;
}
```
## 欧拉定理
### 基本定理
若 $\gcd(a,m)=1$，则 $a^{\varphi(m)}\equiv 1 \pmod m$。
证明参考 [欧拉定理证明](https://zhuanlan.zhihu.com/p/452185813)。
推论：$\gcd(a,m)=1$，则 $a^b \equiv a^{b \% \varphi(m)}\pmod m$。
### 扩展欧拉定理
若 $b > \varphi(m)$，即使 $\gcd(a,m)!=1$，有
$$
a^b \equiv a^{b \bmod \varphi(m)+\varphi(m)} \pmod m
$$
先来一个板子 [P5091 扩展欧拉定理](https://www.luogu.com.cn/problem/P5091)
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,m,b,phi;
bool flag=false;
int calc(int x){
int ans=x;
for(register int 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 ksm(int num,int bas){
int base=num,ans=1;
while(bas){
if(bas&1) ans=ans*base%m;
base=base*base%m;
bas>>=1;
}
return ans;
}
signed main(){
scanf("%lld%lld",&a,&m);
phi=calc(m);
b=read();
if(flag) b+=phi;
cout<<ksm(a,b);
return 0;
}
```
## 例题
### 同余方程
已知 $a,b$ 满足 $\gcd(a,b)=1$，求关于 $x$ 的同余方程 $ax \equiv 1 \pmod b$ 的最小正整数解，$a,b \le 2 \times 10^9$。
类比于 [P1082](https://www.luogu.com.cn/problem/P1082)，但是貌似题目没说互质，但是数据都是互质的……
最好的方法当然是扩展欧几里得，但是这里讨论一下欧拉定理的方法。
那么我们根据欧拉定理，发现 $ax \equiv a^{\varphi(b)} \pmod b$，由于 $\gcd(a,b)=1$，那么我们可以在两边同时除以 $a$，得到 $x \equiv a^{\varphi(b)-1} \pmod b$，则 $x_{min}=a^{\varphi(b)-1} \bmod b$。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
int calc(int x){
int ans=x;
for(register int 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 ksm(int num,int bas){
int base=num,ans=1;
while(bas){
if(bas&1) ans=ans*base%b;
base=base*base%b;
bas>>=1;
}
return ans;
}
signed main(){
cin>>a>>b;
cout<<(ksm(a,calc(b)-1)+b)%b;
return 0;
}
```
### 有理数取余
模板 [P2613 有理数取余](https://www.luogu.com.cn/problem/P2613)。
给出一个有理数 $c = \frac{a}{b}$，求 $c \bmod 19260817$ 的值，其中 $0 \le a,b \le 10^{10001}$ 且 $a,b$ 不同时为 $19260817$ 的质数。
题意等价于 $x \equiv \frac{a}{b} \pmod {19260817}$，求最小的 $x$。
那么我们根据同余方程的性质：
> 如果两个数对模 $p$ 同余，那么它们乘上同一个数以后依然对模 $p$ 同余。
那么我们的柿子就转化成了 $bx \equiv a \pmod {19260817}$。
但是同余 $a$ 并不是我们想要得到的，所以根据上面说的性质，我们尝试找到一个 $x_1$，满足 $bx_1 \equiv 1 \pmod {19260817}$。
那么此时的柿子就变成了 $a \times (bx_1) \equiv a \pmod {19260817}$。
注意到这个柿子与 $bx \equiv a \pmod {19260817}$ 其实是等价的，因为 $bx_1 \bmod 19260817 =1$。
所以答案就应该为 $a \times x_1 \bmod 19260817$。
对于 $x_1$，明显是个经典问题：[P1082](https://www.luogu.com.cn/problem/P1082)。
最后解决 $a,b$ 高精的问题。
其实吧，你把这个因数一直模下去，答案也不会产生变化，即
$$
(b \bmod p) \times x \equiv (a \bmod p) \pmod {p}
$$
对于无解的情况，即 $b \bmod {p} = 0$。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=19260817;
int a,b;
int read(){
int sss=0;
char chh=getchar();
while(chh<'0'||chh>'9') chh=getchar();
while(chh>='0'&&chh<='9'){
sss=sss*10+chh-'0';
sss%=mod;
chh=getchar();
}
return sss;
}
int calc(int x){
int ans=x;
for(register int 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 ksm(int num,int bas){
int base=num,ans=1;
while(bas){
if(bas&1) ans=ans*base%mod;
base=base*base%mod;
bas>>=1;
}
return ans;
}
int solve(){
return (ksm(b,calc(mod)-1)+mod)%mod;
}
signed main(){
a=read(),b=read();
if(!b) return puts("Angry"),0;
cout<<(solve()*a)%mod;
return 0;
}
```
### [P2158 SDOI2008 仪仗队](https://www.luogu.com.cn/problem/P2158)
其实也就是求有多少个不同的斜率罢了。
观察一下题面，我们可以把矩阵分割为左上以及右下以及中间 $y=x$ 两部分，只需要考虑右下部分以及中间部分就可以了。
我们思考，什么情况下会出现一个点 $(x,y)$ 无法被看到，可得到是 $\gcd(x,y)!=1$ 的时候。
那么就很明显了，只有 $\gcd(x,y)=1$ 的点才能被看到。
那么问题就转化为了：在 $1 \dots n$ 中，有多少对互质的数？
那么欧拉函数就派上用场了。
很明显的是，任意两对互质的数得到的商（也就是斜率）是一定不相同的。
那么我们只需要求出 $\varphi(1) \dots \varphi(n)$ 就行了，最后统计的时候只需要统计到 $\varphi(n-1)$ 就行了，因为右下角的三角形边长只有 $n-1$。
注意中间 $y=x$ 的处理以及 $n=1$ 的特殊情况。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,ans=0;
int phi[40005],prime[40005],tot=0;
void init(){
phi[1]=1;
for(register int i=2;i<=n;i++){
if(!prime[i]){
prime[++tot]=i;//省了一个数组
phi[i]=i-1;
}
for(register int j=1;j<=tot&&i*prime[j]<=n;j++){
prime[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(){
n=read();
if(n==1) return puts("0"),0;
init();
for(register int i=1;i<n;i++) ans+=phi[i];
cout<<ans*2+1;
return 0;
}
```
### [P2303 SDOI2012 Longge 的问题](https://www.luogu.com.cn/problem/P2303)
柿子直接一化就出来了。
$\displaystyle\sum_{i = 1}^{n}\gcd(1,n)=\displaystyle\sum_{d|n}d \times \varphi(\frac{n}{d})
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans=0;
int calc(int x){
int ret=x;
for(register int i=2;i*i<=x;i++){
if(x%i==0){
ret=ret/i*(i-1);
while(x%i==0) x/=i;
}
}
if(x>1) ret=ret/x*(x-1);
return ret;
}
int solve(){
for(register int i=1;i*i<=n;i++){
if(n%i==0){
ans+=calc(i)*(n/i)+i*calc(n/i);
}
}
if((int)sqrt(n)*(int)sqrt(n)==n) ans-=calc((int)sqrt(n))*(int)sqrt(n);
return ans;
}
signed main(){
scanf("%lld",&n);
cout<<solve();
return 0;
}P4139 上帝与集合的正确用法
根据扩展欧拉定理，直接将 p 一直递归下去即可。
但是很恶心的一点是，这道题卡空间！
#include<bits/stdc++.h>
using namespace std;
bool forever;
long long T,mod;
long long phi[10000010];
int prime[10000010],cnt=0;
bool Forever;
void init(int n=1e7+5){
phi[1]=1;
for(register int i=2;i<=n;i++){
if(!prime[i]){
prime[++cnt]=i;
phi[i]=i-1;
}
for(register int j=1;j<=cnt&&i*prime[j]<=n;j++){
prime[prime[j]*i]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
long long ksm(long long num,long long bas,long long mod){
long long base=num,ans=1;
while(bas){
if(bas&1) ans=ans*base%mod;
base=base*base%mod;
bas>>=1;
}
return ans;
}
long long solve(int p){
if(p==1) return 0;
return ksm(2,solve(phi[p])+phi[p],p);
}
signed main(){
//cout<<(&Forever-&forever)/1024/1024<<"MB\n";
init();
T=read();
while(T--){
mod=read();
cout<<solve(mod)<<"\n";
}
return 0;
}咕咕咕……