一、简述
本文章主要介绍欧拉函数以及快速幂的相关算法。
二、欧拉函数
定义
\(1∼N\) 中与 \(N\) 互质的数的个数被称为欧拉函数，记为 \(\phi(N)\)。若在算数基本定理中，\(N=p^{a1}_1p^{a2}_2…p^{am}_m\)，则：\(\phi(N)=N\times\frac{p_1−1}{p_1}\times\frac{p_2−1}{p_2}\times…\times\frac{p_m−1}{p_m}\)。
计算式的证明
情况1
当 \(n=0\) 时，显然，因为 \(n=0\) 时，欧拉函数的计算范围内只有 \(0\)，但是 \(\phi(0)=0\)。
当 \(n=1\) 时，因为 \(1\) 与自身互素，\(\phi(1)=1\)。
情况2
当 \(n\) 为素数时，因为 \(1∼n\) 都不被 \(n\) 整除，所以这些数都与 \(n\) 互素，\(\phi(n)=n-1\)。
情况3
对 \(n\) 进行质因数分解 \(n=p^{a1}_1p^{a2}_2…p^{am}_m\)。
将 \(1∼n\) 中所有 \(p_1,p_2...p_m\) 的倍数去掉，剩余 \(n-(n\sum_\limits{i=1}^m\frac{1}{p_i})\) 个数，由于该过程 \(1∼n\) 中既是 \(p_i\) 又是 \(p_j(i\neq j)\) 倍数的数被重复去除，所以我们需要将这些数加回来，即 \(n-(n\sum_\limits{i=1}^m\frac{1}{p_i})+(n\sum_\limits{j,k=1,j\neq k}^m\frac{1}{p_jp_k})\)，以此类推，我们会发现这是多集合容斥计算式，总结为 \(\phi(N)=N\times\frac{p_1−1}{p_1}\times\frac{p_2−1}{p_2}\times…\times\frac{p_m−1}{p_m}\)。
模板题AcWing873.欧拉函数
题目描述
给定 \(n\) 个正整数 \(a_i\)，请你求出每个数的欧拉函数。
输入格式
第一行包含整数 \(n\)。
接下来 \(n\) 行，每行包含一个正整数 \(a_i\)。
输出格式
输出共 \(n\) 行，每行输出一个正整数 \(a_i\) 的欧拉函数。
数据范围
\(1≤n≤100,\)
\(1≤a_i≤2×10^9\)
输入样例
3
3
6
8
输出样例
2
2
4
解题思路
根据欧拉函数的计算式计算即可，时间复杂度\(O(n\sqrt{a})\)。
C++代码
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
while(n --)
{
int a;
cin >> a;
int res = a;
for(int i = 2; i <= a / i; i ++)
{
if(a % i == 0)
{
res = res / i * (i - 1);
while(a % i == 0)
a /= i;
}
}
if(a > 1) res = res / a * (a - 1);//先除后乘可以避免数值溢出
cout << res << endl;
}
return 0;
}
三、筛法求欧拉函数
思路
借用线性筛进行欧拉函数的计算
模板题AcWing874.筛法求欧拉函数
题目描述
给定一个正整数 \(n\)，求 \(1∼n\) 中每个数的欧拉函数之和。
输入格式
共一行，包含一个整数 \(n\)。
输出格式
共一行，包含一个整数，表示 \(1∼n\) 中每个数的欧拉函数之和。
数据范围
\(1≤n≤10^6\)
输入样例
6
输出样例
12
解题思路
由于数据范围为 \(10^6\)，显然我们不能根据定义去依次计算再求解。我们考虑使用线性筛法的方式区计算，具体思路借助代码解释。
关于代码中 \(flag1\)：根据欧拉函数计算式可知 \(i=p^{a1}_1p^{a2}_2…p^{am}_m\)，\(\phi(i)=i\times\frac{p_1−1}{p_1}\times\frac{p_2−1}{p_2}\times…\times\frac{p_m−1}{p_m}\)；而 \(t=primes[j]\times i\)，而 \(primes[j]\) 整除 \(i\)，故 \(t=p^{a1}_1p^{a2}_2…p^{am}_m\)，除了 \(t\) 的 \(primes[j]\) 的指数比 \(i\) 多一，则 \(\phi(t)=t\times\frac{p_1−1}{p_1}\times\frac{p_2−1}{p_2}\times…\times\frac{p_m−1}{p_m}=primes[j]\times i\times\frac{p_1−1}{p_1}\times\frac{p_2−1}{p_2}\times…\times\frac{p_m−1}{p_m}=primes[j]\times\phi(i)\)。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
typedef long long LL;
int n;
int primes[N], cnt;
int euler[N];
bool st[N];
void get_eulers(int n)
{
euler[1] = 1;//1对应的欧拉函数为1
for(int i = 2; i <= n; i ++)
{
if(!st[i])//i为质数
{
primes[cnt ++] = i;//筛出质数
euler[i] = i - 1;//质数对应的欧拉函数值为本身减1
}
for(int j = 0; primes[j] <= n / i; j ++)
{
int t = primes[j] * i;
st[t] = true;
if(i % primes[j] == 0)//primes[j]为i的一个质因数，同时也是t的质因数
{
//flag1
euler[t] = euler[i] * primes[j];
break;
}
//flag2
euler[t] = euler[i] * (primes[j] - 1);
}
}
}
int main()
{
cin >> n;
get_eulers(n);
LL res = 0;
for (int i = 1; i <= n; i ++ ) res += euler[i];
cout << res << endl;
return 0;
}