欧拉函数和快速幂

欧拉函数：

定义：

互质：互质是公约数只有1的两个整数，叫做互质整数。
欧拉函数：欧拉函数，即 体现的是小于等于n并且和n互质的数的个数。
好比说 φ(1) = 1。当n是质数的时候，显然有 (n)=n-1。
如何求1~n中和n互质的数的个数？

容质原理：
1.从1~n中去掉p1，p2....pk的倍数（此时可能存在多去的环境，例如一个数既是p1的倍数又是p2的倍数）
2.加上全部pi*pj的倍数（此时如果一个数既是p1，p2的倍数又是p3的倍数，此时加三次减三次，没有变化但我们需要去除）
3.减去全部pi*pj*pk
4.加上pi*pj*pk*pd....
依次类推合并得到

，其中p1，p2.....pn是n的质因子
题目：

1. #include<bits/stdc++.h>
2. using namespace std;
3. /*
4. 先试除法分解质因数，在分解过程中如果遇到质因子，那么就用公式计算欧拉函数的结果
5. */
6. int main() {
7.     int n; cin >> n;
8.     while(n--){
9.         int x; cin >> x;
10.         int res = x;
11.         for(int i = 2; i < x / i; i++){
12.             if(x % i == 0){
13.                 // 为了除尽，将res * (1 - 1/i) -> res * (i - 1) / i
14.                 res = res * (i - 1) / i;
15.                 while(x % i == 0) x /= i;
16.             }
17.         }
18.         if(x > 1) res = res * (x - 1) / x;
19.         cout << res << '\n';
20.       
21.     }
22.     return 0;
23. }

复制代码

 筛法求欧拉函数:

求1~n之间全部数的欧拉函数就可以用筛选法

1. #include<bits/stdc++.h>
2. using namespace std;
3. using ll = long long;
4. const int N = 1e6+10;
5. int cnt,prime[N],phi[N];
6. bool st[N];
7. ll get_eulers(int n){
8.     phi[1] = 1;
9.     for(int i = 2; i <= n; i++){
10.         if(!st[i]){
11.             //质数
12.             prime[cnt++] = i;
13.             phi[i] = i - 1;
14.         }
15.         // 质数的倍数标记为不是质数
16.         for(int j = 0; prime[j] <= n / i; j++){
17.             st[prime[j] * i] = true;
18.             // Prime[j]是i其中的质因子
19.             if(i % prime[j] == 0){
20.                 phi[prime[j] * i] = phi[i] * prime[j];
21.                 break;
22.             }
23.             phi[prime[j]*i] = phi[i] * (prime[j] - 1);
24.         }
25.     }
26.     ll res = 0;
27.     for(int i = 1; i <= n; i++) res += phi[i];
28.     return res;
29. }
30. int main() {
31.     int n; cin >> n;
32.     cout << get_eulers(n) <<'\n';
33.     return 0;
34. }

复制代码

 
快速幂：

快速幂：

快速幂算法的目标是计算

。传统的做法是通过循环将 a 一连乘 k 次，时间复杂度是 O(k)。但快速幂算法利用了二进制体现的特性，将这个过程优化到了 O(log⁡k)

b个数之间我们不难发现规律：每一个数都是前一个数平方%p。

题目：

1. #include<bits/stdc++.h>
2. using namespace std;
4. int n;
5. int ksm(int a,int k,int p){
6.     int res = 1;
7.     while(k){
8.         //如果在二进制当中该位是1的话就要累乘到res中
9.         if(k & 1) res = (ll) res * a % p;
10.         k >>= 1;// 相当处理下一位
11.         //每一个数都是前一个数平方%p
12.         a = (ll)a * a % p;
13.     }
14.     return res;
15. }
17. int main() {
18.     scanf("%d",&n);
19.     while(n--){
20.         int a,k,p;
21.         scanf("%d %d %d",&a,&k,&p);
22.         printf("%d\n",ksm(a,k,p));
23.     }
24.     return 0;
25. }

复制代码

快速幂求逆元：

对于这类题目，其实就是找到一个数x，可以或许使得

。
根据费马小定理：

我们可以知道对于素数来说，

，所以对于a来说

。
故对于质数a来说，该逆元就是

。
至于无解的环境就是a是p的倍数，此时

，不可能为1。
题目：

 

1. #include<bits/stdc++.h>
2. using namespace std;
3. using ll = long long;
4. int n;
5. int ksm(int a,int k,int p){
6.     int res = 1;
7.     while(k){
8.         //如果在二进制当中该位是1的话就要累乘到res中
9.         if(k & 1) res = (ll) res * a % p;
10.         k >>= 1;// 相当处理下一位
11.         //每一个数都是前一个数平方%p
12.         a = (ll)a * a % p;
13.     }
14.     return res;
15. }
17. int main() {
18.     scanf("%d",&n);
19.     while(n--){
20.         int a,p;
21.         //如果a是p的倍数那么一定无解
22.         //如果 不是，根据费马定理可以构造出解
23.         scanf("%d %d",&a,&p);
24.         int res = ksm(a,p-2,p);
25.         //p == 2的时候，一定返回的是1
26.         if(a % p) printf("%d\n",res);
27.         else puts("impossible");
28.     }
29.     return 0;
30. }

复制代码

 

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。