文章目录
前言
一、欧拉函数，欧拉定理
二、例题，代码
AcWing 873. 欧拉函数
AC代码
AcWing 874. 筛法求欧拉函数
本题解析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解数学知识：欧拉函数，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、欧拉函数，欧拉定理
欧拉函数的公式：
首先我们把一个数分解质因子，分解的方法见：数学知识：质数，把一个数化成如下图形式：
计算欧拉函数：
对于上图的推导：建议百度（面向百度编程
欧拉定理：如果a和b是互质的那么一定有：
对于上图的推导：建议百度（面向百度编程
特殊的，当b为质数的时候有：
上图中的式子也被称为费马定理.
二、例题，代码
AcWing 873. 欧拉函数
本题链接：AcWing 873. 欧拉函数
本博客提供本题截图：
AC代码
#include <iostream> using namespace std; int phi(int x) { int res = x; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { res = res / i * (i - 1); while (x % i == 0) x /= i; } if (x > 1) res = res / x * (x - 1); return res; } int main() { int n; cin >> n; while (n -- ) { int x; cin >> x; cout << phi(x) << endl; } return 0; }
AcWing 874. 筛法求欧拉函数
本题链接：AcWing 874. 筛法求欧拉函数
本博客提供本题截图：
本题解析
本题核心为：如果数k是质数，那么这个数的欧拉函数为k - 1，如果不是质数的话，满足：
int t = primes[j] * i; if (i % primes[j] == 0) euler[t] = euler[i] * primes[j]; euler[t] = euler[i] * (primes[j] - 1);
AC代码
#include <iostream> using namespace std; typedef long long LL; const int N = 1000010; int primes[N], cnt; int euler[N]; bool st[N]; void get_eulers(int n) { euler[1] = 1; for (int i = 2; i <= n; i ++ ) { if (!st[i]) { primes[cnt ++ ] = i; euler[i] = i - 1; } for (int j = 0; primes[j] <= n / i; j ++ ) { int t = primes[j] * i; st[t] = true; if (i % primes[j] == 0) { euler[t] = euler[i] * primes[j]; break; } euler[t] = euler[i] * (primes[j] - 1); } } } int main() { int n; cin >> n; get_eulers(n); LL res = 0; for (int i = 1; i <= n; i ++ ) res += euler[i]; cout << res << endl; return 0; }
三、时间复杂度
关于欧拉函数各步操作的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
