哈尔滨网站快速排名,网站采集被降权,最新军事新闻热点事件,茂港手机网站建设公司文章目录 AcWing 873. 欧拉函数题目链接欧拉函数欧拉函数的证明思路CODE时间复杂度分析 AcWing 874. 筛法求欧拉函数题目链接问题分析与时间复杂度CODE思路 欧拉定理 AcWing 873. 欧拉函数
题目链接
https://www.acwing.com/activity/content/problem/content/942/ 欧拉函数 … 文章目录 AcWing 873. 欧拉函数题目链接欧拉函数欧拉函数的证明思路CODE时间复杂度分析 AcWing 874. 筛法求欧拉函数题目链接问题分析与时间复杂度CODE思路 欧拉定理 AcWing 873. 欧拉函数
题目链接
https://www.acwing.com/activity/content/problem/content/942/ 欧拉函数
对于正整数 n n n欧拉函数是小于或等于 n n n 的正整数中与 n n n 互质的数的数目记作 φ ( n ) φ(n) φ(n) φ ( 1 ) 1 φ(1)1 φ(1)1 欧拉函数的证明
基于容斥原理 所以归纳得到公式 K N ( 1 − 1 / p 1 ) ( 1 − 1 / p 2 ) . . . ( 1 − 1 / p i ) K N(1 - 1/p1)(1 - 1/p2)...(1 - 1/pi) KN(1−1/p1)(1−1/p2)...(1−1/pi) 思路
按照分解质因数的逻辑挨个得到质因数然后累乘即可。 CODE
#include iostream
#include cstring
#include algorithmusing 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;scanf(%d, n);while (n -- ){int a;scanf(%d, a);cout phi(a) endl;}
}时间复杂度分析
复杂度瓶颈在于分解质因数所以是 O ( n ) O(\sqrt{n}) O(n ) AcWing 874. 筛法求欧拉函数
题目链接
https://www.acwing.com/activity/content/problem/content/943/ 问题分析与时间复杂度
对于范围内的每个数都求欧拉函数肯定不能用定义法一个一个求这样时间复杂度为 O ( n ⋅ n ) O(n·\sqrt n) O(n⋅n )我们可以用线性筛筛出质数再计算质因数时间复杂度为 O ( n ) O(n) O(n) CODE
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 1e6 10;
int primes[N], eulers[N], cnt;
bool st[N];void get_eulers(int n){eulers[1] 1;for(int i 2; i n; i){if(!st[i]){primes[cnt] i;eulers[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){eulers[t] eulers[i] * primes[j];break;}eulers[t] eulers[i] * (primes[j] - 1);}}
}int main(){int n;scanf(%d, n);get_eulers(n);long long res 0;for(int i 1; i n; i) res eulers[i];cout res endl;
}思路
主要有三点
如果 i 是质数那么[1, i - 1]都是i的质因数所以有eulers[i] i - 1;如果 i 不是质数那么它会被筛掉这里有两种情况 primes[j]是i的最小质因子时 i * primes[j]的欧拉函数是这样的 K i ∗ p r i m e s [ j ] ∗ ( 1 − 1 / p 1 ) . . . ( 1 − 1 / p i ) K i * primes[j] * (1 - 1/p1)...(1 - 1/pi) Ki∗primes[j]∗(1−1/p1)...(1−1/pi)我们会发现整个式子化简得到 K e u l e r s [ i ] ∗ p r i m e s [ j ] K eulers[i] * primes[j] Keulers[i]∗primes[j]也就是说是i的欧拉函数乘上了最小质因子primes[j]的值。 primes[j]不是i的最小质因子时 i * primes[j]的欧拉函数是这样的 K i ∗ p r i m e s [ j ] ∗ ( 1 − 1 / p 1 ) . . . ( 1 − 1 / p i ) ( 1 − 1 / p r i m e s [ j ] ) K i * primes[j] * (1 - 1/p1)...(1 - 1/pi)(1 - 1/primes[j]) Ki∗primes[j]∗(1−1/p1)...(1−1/pi)(1−1/primes[j])虽然primes[j]不是i的最小质因子但是是primes[j] * i的最小质因子所以需要多乘上 1 − 1 / p r i m e s [ j ] 1 - 1/primes[j] 1−1/primes[j]。化简得 K e u l e r s [ i ] ∗ ( p r i m e s [ j ] − 1 ) K eulers[i] * (primes[j] - 1) Keulers[i]∗(primes[j]−1) 欧拉定理
若 a a a 与 n n n 互质则 a φ ( n ) ≡ 1 ( m o d n ) a^{φ(n)} ≡ 1(mod\ n) aφ(n)≡1(mod n)
证明 1 1 1 ~ n n n 中设 n n n 的欧拉函数为 a 1 , a 2 , . . . , a φ ( n ) a_1, a_2, ...\ , a_{φ(n)} a1,a2,... ,aφ(n)那么全部乘上 a a a 得到 a a 1 , a a 2 , . . . , a a φ ( n ) aa_1, aa_2, ...\ ,aa_{φ(n)} aa1,aa2,... ,aaφ(n)那么得到如下式子 a φ ( n ) ( a 1 , . . . , a i ) ≡ ( a 1 , . . . , a i ) ( m o d n ) a^{φ(n)}(a_1, ...\ , ai) ≡ (a1, ...\ ,ai)\ \ (mod\ n) aφ(n)(a1,... ,ai)≡(a1,... ,ai) (mod n)两边消去得到欧拉定理 a φ ( n ) ≡ 1 ( m o d n ) a^{φ(n)} ≡ 1(mod\ n) aφ(n)≡1(mod n) 当 n , a n, a n,a 互质时可以得到费马定理 a n − 1 ≡ 1 ( m o d n ) a^{n - 1} ≡ 1(mod\ n) an−1≡1(mod n)
