算法中的数学：欧拉函数

1.相关定义

互质：a与b的最大公约数为1

欧拉函数：在1~n中，与n互质的数的个数就是欧拉函数的值

eg：

n=1时，欧拉函数的值为1，因为1和1是互质的

n=2是，值为2，因为1和2都是互质的

积性函数：f(1）= 1且f(xy) = f(x)f(y)，其中x与y互质

2.欧拉函数

性质：
1.若p为质数，则：φ(p) = p-1

解析：

因为p是质数，所以在1~p中与p有除了1以外的公约数的只有p本身，总共的数的个数为p，所以与p互质的数就是p-1个，即φ(p) = p-1
2.若p为质数，则：φ(p^k) = (p-1)p^(k-1)

解析：
对p^k进行分解质因数：p^k = p*p*p*p...*p（共k个）

我们发现p^k只有p本身，而p是质数，不能由其他数组合而成，所以p^k只能与p的倍数有除了1以外的公约数，而我们以每一个倍数的p为一个周期看待，每个周期内有p-1个与p^k

互质的数

3.欧拉函数属于积性函数

即φ(xy) = φ(x)φ(y)

3.试除法求单个数欧拉函数 

公式解释：单个数n的欧拉函数就是n乘上(pi-1)/pi的连乘

公式推导：

1.对n分解质因数

2.由于欧拉函数是积性函数，所以我们可以直接拆分开

3.由于pi是质数，根据欧拉函数的性质（若p为质数，则：φ(p^k) = (p-1)p^(k-1)），得到结果式子

4.我们将pi^(αi-1)中的pi^(-1)分离出去给到(pi-1)，于是就得到了(pi-1)/pi

5.根据pi的连乘是n分解质因数的得到的，所以pi的连乘换成n，得证

代码实现：
 

int phi(int n)
{int answer = n;for (int i = 2; i <= n / i; i++){if (n % i == 0){answer = answer / i * (i - 1);//先除后乘防止溢出while (n % i == 0) n /= i;}}if (n > 1) answer = answer / n * (n - 1);return answer;
}

4.欧拉筛打表欧拉函数

我们可以在进行线性筛的时候顺便计算记录下对应数据的欧拉函数

线性筛代码如下：
 

typedef long long ll;
const int N = 1e9;
bool f[N];
int a[N];
int count;
void get_prime(int n)
{for(ll i = 2; i <= n; i++){
//没有被标记为true，说明是质数if(f[i] == false) {a[++count] = i;}
//进行线性筛for(int j = 1; i*a[j] <= n; j++){f[i*a[j]] = true;if(i % a[j] == 0) break;{          }
}

若数据是质数：根据欧拉函数的性质，欧拉函数的值就是该数-1

若数据不是质数：

（1）i%a[j] != 0：且a[j]是质数，所以i与a[j]互质，此时根据欧拉函数的性质

（φ(xy) = φ(x)φ(y)）可知，φ(x) = φ(i）*φ(a[j])

（2）i%a[j] == 0: φ(x) = φ(i)*a[j]

证明如下：

打表代码：
 

typedef long long ll;
const int N = 1e9;
bool f[N];
int a[N];
int count;
int phi[N];
void get_prime(int n)
{phi[1] = 1;for(ll i = 2; i <= n; i++){
//没有被标记为true，说明是质数if(f[i] == false) {a[++count] = i;phi[i] = i - 1;}
//进行线性筛for(int j = 1; i*a[j] <= n; j++){int x = i * a[j];f[i*a[j]] = true;if(i % a[j] == 0) {phi[x] = a[j] * phi[i];break;}else{phi[x] = phi[i] * (p[j]-1);}}          }
}

5.例题讲解

 

审题：

本题需要我们找到从坐标原点出发可以直接看到的坐标个数

思路：
方法一：分析+欧拉函数

我们建立坐标徐后可以清楚发现，只要点在同一条从原点出发的直线路径上，就只有第一个点可以被直接看到，其他的点都会被遮住。

而被遮住的点可以通过除以横纵坐标的最大公约数变成第一个可以被看见的点，由于这个特性，我们发现最大公约数不为1的横纵坐标的点都会被遮住（因为他们都可以转换成直线上第一个被看见的点）

故可以被看见的点就是横纵坐标互质的点，接下来我们分析如何求

首先我们分析第五列的点（先不看在坐标轴上的点），我们发现横纵坐标互质的点的个数（可以被看到的数）其实就是当前横坐标的欧拉函数。

故我们可以直接将1~n-1的数的欧拉函数累加起来，然后就得到了下半边的可看到点位数，再根据对称轮换，我们对结果乘2可以得到上下两边的可看到点数。但是此时我们的（1,1）被计算了两次（要减1），而坐标轴上的（1,0）和（0,1）两点还没加上（要加2），综合起来我们就要在当前结果的基础上加一.

解题：

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 4e4 + 10;
int n;
//线性筛所需变量
bool st[N];
ll p[N],cnt;
ll phi[N];//欧拉函数
void get_phi()
{phi[1] = 1;for (ll i = 2; i <= n; i++){if (!st[i]){p[++cnt] = i;phi[i] = i - 1;}for (ll j = 1; i * p[j] <= n; j++){st[i * p[j]] = true;ll x = i * p[j];if (i % p[j] == 0){phi[x] = phi[i] * p[j];break;}else//i 与p[j]互质{phi[x] = phi[i] * (p[j] - 1);}}}
}
int main()
{cin >> n;get_phi();ll sum = 0;for (int i = 1; i < n; i++){sum += phi[i];}if (n == 1) cout << 0 << endl;elsecout << sum * 2 + 1 << endl;return 0;
}

其中计算欧拉函数就是使用线性筛来完成。

注意：累加的时候不要加到i==n的情况，因为我们的坐标是从0开始的，所以访问到i==n其实就是越界访问

P2158 [SDOI2008] 仪仗队 - 洛谷