欧拉φ函数：在数论中，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数、欧拉商数等。
φ(1)=1; φ(2)=1; φ(3)=2; φ(4)=2; φ(9)=6
欧拉φ函数
1int GetEuler(int n) { //欧拉函数
2 int res = n;
3 for(int i = 2;i*i <= n; ++i){
4 if(a%i == 0){
5 res -= res/i;
6 while(n%i == 0)
7 n /= i;
8 }
9 }
10 if(a > 1) // 因为是遍历到sqrt(n)，所以可能存在未除尽或者n本身就为质数的情况
11 res -= res/n;
12 return res;
13}
14
15int Phi(int x) { //欧拉函数
16 int i, re = x;
17 for (i = 2; i * i <= x; i++)
18 if (x % i == 0) {
19 re /= i;
20 re *= i - 1;
21 while (x % i == 0)
22 x /= i;
23 }
24 if (x ^ 1) re /= x, re *= x - 1;
25 return re;
26}
欧拉降幂公式
ab(modc) = abmodφ(c)+φ(c)mod(c)
快速幂
1LL quickPow(LL x, LL y, LL mod) {
2 LL res = 1;
3 for (; y; y >>= 1, x = x * x % mod)
4 if (y & 1)res = res * x % mod;
5 return res;
6}
7
8long long quickPow(long long a, int n) {
9 long long answer = 1;
10 for (; n; n /= 2, a = a * a % mod)
11 if (n % 2 == 1) answer = answer * a % mod;
12 return answer % mod;
13}
应用题目
题目目标：2的n次方MOD1e9+7（1<=n<=10100000）
1#include<iostream>
2#include<cstring>
3
4using namespace std;
5typedef long long LL;
6const int MOD = 1e9 + 7;
7
8int GetEuler(int n) //欧拉函数
9{
10 int i;
11 int res = n, a = n;
12 for (i = 2; i * i <= a; ++i) {
13 if (a % i == 0) {
14 res -= res / i;
15 while (a % i == 0)
16 a /= i;
17 }
18 }
19 if (a > 1)
20 res -= res / a;
21 return res;
22}
23
24LL quickPow(LL x, LL y, LL mod) {
25 LL res = 1;
26 for (; y; y >>= 1, x = x * x % mod)
27 if (y & 1)res = res * x % mod;
28 return res;
29}
30
31char n[100006];
32char m[100006];
33
34int main() {
35
36 scanf("%s %s", n, m);
37 int phi_c = GetEuler(MOD);
38 int len = strlen(n);
39 LL sum = 0;
40 for (int i = 0; i < len; ++i) {
41 sum = (sum * 10 + n[i] - '0') % phi_c;
42 }
43 cout << quickPow(2,sum+phi_c,MOD) << endl;
44}
快速幂方法推导
算法1.直接设计算法
1int ans = 1;
2for(int i = 1;i<=b;i++)
3{
4 ans = ans * a;
5}
6ans = ans % c;
缺点：这个算法存在着明显的问题，如果a和b过大，很容易就会溢出。
我们先来看看第一个改进方案：在讲这个方案之前，要先看这样一个公式：ab mod c = (a mod c)b mod c
算法2.改进算法
1int ans = 1;
2a = a % c; //加上这一句
3for(int i = 1;i<=b;i++)
4{
5 ans = ans * a;
6}
7ans = ans % c;
既然某个因子取余之后相乘再取余保持余数不变，那么新算得的ans也可以进行取余，所以得到比较良好的改进版本。
算法3.进一步改进算法
1int ans = 1;
2a = a % c; //加上这一句
3for(int i = 1;i<=b;i++)
4{
5 ans = (ans * a) % c;//这里再取了一次余
6}
7ans = ans % c;
这个算法在时间复杂度上没有改进，仍为O(b)，不过已经好很多的，但是在c过大的条件下，还是很有可能超时，所以，我们推出以下的快速幂算法。
算法4.快速幂算法
快速幂算法依赖于以下明显的公式：
ab mod c = ((a2)b/2) mod c ,b是偶数
ab mod c = ((a2)b/2×a) mod c ,b是奇数
1int PowerMod(int a, int b, int c)
2{
3 int ans = 1;
4 a = a % c;
5 while(b>0) {
6 if(b % 2 = = 1)
7 ans = (ans * a) % c;
8 b = b/2;
9 a = (a * a) % c;
10 }
11 return ans;
12}
本算法的时间复杂度为O(logb)
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。