哪个网站可以做名片,深圳住房和建设局网站登录界面,建设论坛网站视频,酒类网站该怎么做文章目录 欧拉函数定义性质 例题列表873. 欧拉函数#xff08;使用质因数分解求一个数的欧拉函数#xff09;原理讲解#xff08;公式推导#xff09;⭐解法代码 874. 筛法求欧拉函数#xff08;求 1 ~ n 中所有数字的欧拉函数#xff09;⭐ 欧拉函数
https://oi-wiki.o… 文章目录 欧拉函数定义性质 例题列表873. 欧拉函数使用质因数分解求一个数的欧拉函数原理讲解公式推导⭐解法代码 874. 筛法求欧拉函数求 1 ~ n 中所有数字的欧拉函数⭐ 欧拉函数
https://oi-wiki.org/math/number-theory/euler/
定义 即 1 ~ n 中和 n 互质的数字个数。
Q怎么判断两个数是互质的 A两个数的 最大公约数为1。比如 1 和 1 就是互质的
性质 求 φ ( n ) \varphi(n) φ(n) 即 先完成质因数分解然后按公式计算。
例题列表
873. 欧拉函数使用质因数分解求一个数的欧拉函数
https://www.acwing.com/activity/content/problem/content/942/ 原理讲解公式推导⭐
使用 容斥原理 计算出 ——
1 ~ N 中所有质数的个数是 化简之后就是公式了。 解法代码
记住公式 使用质因数分解求出 n 的所有的质因子。 使用所有质因子按照公式计算 n 的欧拉函数。题目中也给出了公式
import java.util.*;public class Main {public static void main(String[] args){Scanner sc new Scanner(System.in);int n sc.nextInt();while (n-- ! 0) {System.out.println(euler(sc.nextInt()));}}static long euler(int n) {long res n;for (int i 2; i n / i; i) {if (n % i 0) {while (n % i 0) n / i;res res * (i - 1) / i;}}if (n 1) res res * (n - 1) / n;return res;}
}
874. 筛法求欧拉函数求 1 ~ n 中所有数字的欧拉函数⭐
https://www.acwing.com/activity/content/problem/content/943/ 在欧氏筛质数的过程中计算欧拉函数。
使用到的一些欧拉函数的性质
质数 x x x 的欧拉函数是 x − 1 x - 1 x−1。对于 t p [ j ] ∗ i t p[j] * i tp[j]∗i。当 i i % p[j] 0 i 时即 p [ j ] p[j] p[j] 也是 i i i 的质因子则 t i ∗ p [ j ] t i * p[j] ti∗p[j] 的质因子和 i i i 的质因子一样因此 e u l e r [ t ] p [ j ] ∗ e u l e r [ i ] euler[t] p[j] * euler[i] euler[t]p[j]∗euler[i]。对于 t p [ j ] ∗ i t p[j] * i tp[j]∗i。当 i i % p[j] ! 0 i 时即 p [ j ] p[j] p[j] 不是 i i i 的质因子则 t i ∗ p [ j ] t i * p[j] ti∗p[j] 的质因子比 i i i 的质因子多了一个 p [ j ] p[j] p[j]因此 e u l e r [ t ] p [ j ] ∗ e u l e r [ i ] ∗ ( 1 − 1 / p [ j ] ) ( p [ j ] − 1 ) ∗ e u l e r [ i ] euler[t] p[j] * euler[i] * (1 - 1 / p[j]) (p[j] - 1) * euler[i] euler[t]p[j]∗euler[i]∗(1−1/p[j])(p[j]−1)∗euler[i]。
import java.util.*;public class Main {final static int N 1000001;static int cnt 0;static int[] primes new int[N], euler new int[N];static boolean[] st new boolean[N]; // 是否被筛掉了public static void main(String[] args){Scanner sc new Scanner(System.in);int n sc.nextInt();euler[1] 1; // 初始化欧拉数组// 欧氏筛质数for (int i 2; i n; i) {if (!st[i]) { // 如果 i 没有被筛掉是质数primes[cnt] i;euler[i] i - 1; // 质数的 x 的欧拉函数是 x - 1 (去掉它本身)}// 筛掉所有 primes[j] 的 i 倍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]; // t和i的质因子一样break;}euler[t] euler[i] * (primes[j] - 1); // t的质因子比i多了一个p[j]}}long ans 0; // 答案会超 int所以使用 longfor (int i 1; i n; i) {ans euler[i];}System.out.println(ans);}
}
在 欧式筛的过程中利用上面提到的一些性质来筛出 1 ~ n 的所有欧拉函数。