欧拉函数&欧几里得算法学习笔记
chinaxjh
2019-11-10 14:45:56
# 欧拉函数
# Part 1
### 什么是欧拉函数
在数论，对正整数$n$，欧拉函数是小于或等于$n$的正整数中与$n$互质的数的数目，记作$φ(n)$
# Part 2
### 引理
- 1.如果$n$为某一个素数$p$，则
$$φ(p)=p-1$$
- 2.如果$n$为某一个素数$p$的幂次，那么
$$φ(p^a)=(p-1)*p^{(a-1)}$$
- 3.如果n为任意两个数$a$和$b$的积，条件是$a$与$b$互质,那么
$$φ(a*b)=φ(a)*φ(b)$$
- 4.设 (为$n$的分解式)
$$n=(p1^{a1})*(p2^{a2})*……*(pk^{ak})$$
那么
$$φ(n)=n*(1-1/p1)*(1-1/p2)*……*(1-1/pk)$$
- 5.欧拉定理：($a$与$m$互质)
$$a^{φ(m)}≡1(mod\quad m)$$
- 5.$x$.欧拉定理的推论($a$,$m$互质)
$$a^{b}≡a^{b \quad mod\quad φ(m)}(mod\quad m)$$
- 6.扩展欧拉定理$b≥φ(m)$时,
$$a^b ≡a^{(b\quad mod\quadφ(m))+φ(m)} (mod\quad m)$$
- 7.费马小定理(乱入的费马)
由引理$1,5$可得
$$a^{p-1}≡1(mod\quad p)$$
# Part 3
### 欧拉函数怎么求
#### 单个求解
根据定义
- 老师，我会暴力
```cpp
int gcd(int x,int y)
{
if (y==0) return x;
return gcd(y,x%y);
}
int phi(int x)
{
int i,ans;
ans=0;
for (i=1;i<=x;i++)
if (gcd(x,i)==1) ans++;
return ans;
}
```
根据引理4
- 老师，我会瞎搞
```cpp
//建议ans用double
ll phi(ll x)
{
ll i,ans,xx;
xx=x;
ans=x;
for (i=2;i*i<=xx;i++)
if (xx%i==0)
{
while (xx%i==0) xx/=i;
ans=(int)ans*(double)(1-(double)1/i);
}
if (xx>1)
{
ans=(int)ans*(double)(1-(double)1/xx);
}
return ans;
}
```
#### 多个求解
- 老师，我会瞎搞
```cpp
//建议ans用double
ll phi(ll x)
{
ll i,ans,xx;
xx=x;
ans=x;
for (i=2;i*i<=xx;i++)
if (xx%i==0)
{
while (xx%i==0) xx/=i;
ans=(int)ans*(double)(1-(double)1/i);
}
if (xx>1)
{
ans=(int)ans*(double)(1-(double)1/xx);
}
return ans;
}
for (ll i=1;i<=n;i++)
printf("%lld\n",phi(i));
```
- 老师，我会筛法
```cpp
double phi[N];
ll phi(ll k)
{
ll i,j;
for (i=1;i<=k;i++)
phi[i]=i;
for (i=2;i<=k;i++)
if (phi[i]==i)
{
phi[i]--;
p[++len]=i;
for (j=2;j<=k/i;j++)
phi[j*i]=phi[j*i]*(double)((double)1-(double)1/i);
}
}
```
# Part 4
### 例题
##### P2158[SDOI2008]仪仗队
欧拉函数裸题，不过需要$get$线性求法
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10000005;
ll p[N],n,m,k,i,ans;
double phi[N];
ll phiall(ll k)
{
ll i,j;
for (i=1;i<=k;i++)
phi[i]=i;
for (i=2;i<=k;i++)
if (phi[i]==i)
{
phi[i]--;
for (j=2;j<=k/i;j++)
phi[j*i]=phi[j*i]*(1-((double)1/i));
}
}
int main()
{
cin>>n;
phiall(n);
if (n==1)
{
printf("%d",0);
return 0;
}
for (i=0;i<=n-1;i++) ans+=phi[i];
cout<<ans*2+1<<endl;
}
```
##### GCD
推出公式就好了
设
$$gcd(x,y)=1\quad (x>y)$$
那么把他们乘上一个相同的质数$p$
$$gcd(x*p,y*p)=p$$
由此可见，对于每一对满足条件的$x$,$y$，只要找出在$N/x$以内的质数个数，就是这对$x$,$y$，对答案的贡献
考虑$φ(n)$为在$n$以内与$n$互质的数的个数，由于这个数必然小于$n$，故$(2<=p<=N/n)$，可以在求$φ$的同时求出素数个数
**注意(2,4),(4,2)算两种情况**
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
long long ans;
int i,n,p[N];
double a[N];
void serve(int x)
{
int i,j;
for (i=1;i<=x;i++)
a[i]=i;
for (i=2;i<=x;i++)
if (a[i]==i)
{
a[i]=i-1;
p[i]=p[i-1]+1;
for (j=2;j<=x/i;j++)
a[i*j]=a[i*j]*(double)(1-(double)1/i);
} else p[i]=p[i-1];
}
int main()
{
cin>>n;
serve(n);
for (i=1;i<=n;i++)
ans+=a[i]*p[n/i];
cout<<ans*2-p[n]<<endl;
}
```
##### P4139 上帝与集合的正确用法
具体看我写的[题解](https://www.luogu.org/blog/chinaxjh/solution-p4139)
# （扩展）欧几里得
# Part 0
## 说明
一下所有的$\%$为取模，$/$为整除
# Part 1
## 最基础的模板
欧几里得算法，即
$$gcd(x,y)=gcd(x, x\%y )$$
当$y=0$时，答案即为$x$
## 引出的知识
### $Bézout$定理
**对于任意整数$a$,$b$,存在一对整数$x$,$y$,满足$ax+by=gcd(a,b)$**
# Part 2
## 扩展欧几里得
先看一个例题，[$NOIP2012$同余方程](https://www.luogu.org/problem/P1082)
一句话题意，给出$a$,$b$和式子
$$ax≡1(mod \quad b)$$
求解最小的正整数$x$
### 算法1
#### 费马小定理
若$b$为质数，则
$$a^{b-1}≡1(mod \quad b)$$
化开成为
$$a * a^{b-2}≡1(mod \quad b)$$
$a^{b-2}$即为所求的一个$x$(注意不是最小正整数解)，我们可以通过取余操作把它变成最小正整数解
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,p;
ll qpow(ll x,ll y)
{
ll t;
if (y==1) return x%p;
if (y==0) return 1;
t=qpow(x,y/2);
t=t*t%p;
if (y%2==0) return t;
else return t*x%p;
}
int main()
{
cin>>a>>b;
p=b;
cout<<(qpow(a,b-2)%b+b)%b<<endl;
}
```
但可惜这道题没有保证$b$为质数，实测只有20分
### 算法2
#### 扩展欧几里得
~~如果这道题都被费马这个业余数学家给搞掉了，还要我欧几里得何用~~
对于
$$ax≡1(mod \quad b)$$
设
$$ax+by=1=gcd(a,b)$$
由欧几里得算法可知
$$ax+by=bx'+(a\%b)y'=gcd(a,b)=1$$
提出
$$bx'+(a\%b)y'$$
化简
$$bx'+(a-(a/b) * b)* y'$$
$$bx'+ay'-(a/b)* b* y'$$
$$ay'+b(x'-(a/b)* y')$$
显然
$$x=y'$$
$$y=x'-(a/b)* y'$$
可以使式子恒成立
注意边界$gcd(a,b)=gcd(b,0)$时，在此题中，若$x=1,y=0$显然可以使式子成立
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,x,y;
void exgcd(ll a,ll b,ll &x,ll &y)//一定要写&
{
ll t;
if (b==0)
{
x=1; y=0;
}
else
{
exgcd(b,a%b,x,y);
t=x; x=y; y=t-(a/b)*y;
}
}
int main()
{
scanf("%lld%lld",&a,&b);
exgcd(a,b,x,y);
cout<<((x+b)%b+b)%b<<endl;//多取几次模把答案移到最小正整数解
}
```
# Part 3
## 例题
### 青蛙的约会
[题目](https://www.luogu.org/problem/P1516)
由题意推公式
$$am+x≡an+y(mod\quad L)$$
$$a(m-n)≡y-x(mod\quad L)$$
设
$$m-n=k\quad y-x=t$$
得
$$ka≡t(mod\quad L)$$
再设
$$ka+bL=t$$
由$Bézout$定理可得，当
$$ t|gcd(k,L) $$
时，原不定方程有解
所以我们可以在求解$exgcd$的同时得出它们的$gcd$，然后判定有无解
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll xx,yy,x,y,m,n,l,a,b,ans,p;
void exgcd(ll a,ll b,ll &x,ll &y)
{
ll t;
if (b==0)
{
p=a;
x=1; y=0;
}
else
{
exgcd(b,a%b,x,y);
t=x; x=y; y=t-(a/b)*y;
}
}
int main()
{
cin>>x>>y>>m>>n>>l;
if (m==n)
{
puts("Impossible");
return 0;
}
if (m<n)
{
swap(m,n);
swap(x,y);
}
a=m-n;
b=((y-x)%l+l)%l;
exgcd(a,l,xx,yy);
if (b%p!=0)
{
puts("Impossible");
return 0;
}
ans=(xx*(b/p)%(l/p)+l/p)%(l/p);
cout<<ans<<endl;
}
```