快速幂

发表于 更新于

由于我没看网上的分析，于是我看了看思想自己写了一份QwQ

  不保证你能看懂 反正也没有人看

朴素做法

  首先先让我们看看朴素的做法 就说我们平时的一个for的方式 \(eg:\) \[2^7=2^1*2^1*2^1*2^1*2^1*2^1*2^1\] 很明显这样是\(O\left (N \right)\)的 
graph TD;
    A(( $2^7$ ))-->B((2^6));
    A(( 2^7 ))-->C((2^1))
    B(( 2^6 ))-->D((2^5));
    B(( 2^6 ))-->E((2^1))
    D((2^5))---->S((2^1))
    D((2^5))--->F((.....))

  剩下的省略，绝对不是因为懒( ﾟдﾟ)つBye

快速幂法

  然后是快速幂做法 ### 二话不说先上图 
graph LR;
    A(( $2^7$ ))--->B((2^6));
    A(( 2^7 ))--->C((2^1)) --> I;
    B(( 2^6 ))--->D((2^3));
    B(( 2^6 ))--->E((2^3)) --> F;
    D((2^3))-->S((2^1)) -->I;
    D((2^3))--->F((2^2));
    F((2^2)) --> G((2^1)) & H((2^1)) --> I((2^0));
  上图是不是非常好理解啊……ƪ(˘⌣˘)ʃ

被暴打后，口吐白沫
被暴揍.gif

配图如下 快速幂示意图3.jpg

  在这里我们分法不再是1，1，1的分了； 而是尽可能的把大数二分小数 对于偶数，我们直接二分 $ eg:$ \(\qquad 2^8=2^4 \times 2^4\) \(\qquad \quad \; \: \; 2^9=2^8 \times 2^1\) 其实思想就这些,是不是很简单

  那么他的理想复杂度应为\(O\left (\log_2 N \right)\)

那么现在让我们分别用递归和循环来实现

（先别走，后面有大量示例代码）

\(\text{PS: }\)一般的题面都会让你取模，再这里统统省略……

递归法

  看下面的代码就说把思想的BF实现啊 

1
2
3
4
5
6
7
8
9
10
inline int power_operate(int x,int m){
   int ans=1;
   if (m&1){    //判断是不是奇数
       ans=ans*x;
   }
   if (m){
       ans*=quick_power_operate(x,m>>1)*quick_power_operate(x,m>>1);    //这里没有任何优化，直接BF思想向下递归
   }
   return ans;
}
  让我们测试一下，看看 \(eg:\) $^{10} $

1
2
3
1024
--------------------------------
Process exited after 0.4793 seconds with return value 0

\(\qquad \quad \; \: \; 3^{11}\)

  为什么选11次方呢，以为太大了就爆掉了啊……QwQ 

1
2
3
177147
--------------------------------
Process exited after 0.4788 seconds with return value 0
取个模再来一次 \(\qquad \quad \; \: \; 3^{99999999}\)

1
2
3
4
3 的 99999999 次方  模数: 1000
667
--------------------------------
Process exited after 7.806 seconds with return value 0
循环

  这里是不是从上向下的实现，而是从下向上的 这里我还是建议你自己手动debug一下的

1
2
3
4
5
6
7
8
9
10
11
inline int quick_power_operate(int x,int m){
	int ans=1;
	while(m){
		if (m&1){
			ans=ans*x;
		}
			x=xx;
		y>>=1; 
	}
	return ans;
}

  来，让我们那开头的那个例子来吧: \(2^7\)

  这里一步先判断它是不是奇数，是就把它处理为偶数(判断奇数，二进制末尾为1)

graph TB;
    A(( $2^7$ )) --- B((2^6));
    A(( 2^7 )) --- C((2^1));
     A -.step_1.-> C
    B(( 2^6 )) --- E((2^3)) ;
    B(( 2^6 )) --- D((2^3));
    D((2^3)) --- S((2^1)) ;
    D((2^3)) --- F((2^2));
    E --- G((2^2)) & H((2^1))
    G --- I((2^1)) & K((2^1));
    F((2^2)) --- L((2^1)) & M((2^1));

  变成偶数就简单了，从下base(即为底数，这里是2)开始自乘 我这里只画一条线，因为本质就一条……TAT ***

graph TB;  
    A(( $2^7$ )) --- B((2^6));  
    A(( 2^7 )) --- C((2^1));  
     C -.step_1.-> A  
    B(( 2^6 )) --- E((2^3)) ; 
    B(( 2^6 )) --- D((2^3)); 
    E --- G((2^2)) & H((2^1));  
    D((2^3)) --- S((2^1)) ;
    D((2^3)) --- F((2^2));  
    F((2^2)) --- L((2^1)) & M((2^1));  
    G --- I((2^1)) & K((2^1));  
    I -.step_2.-> G   ;
    G -.step_3.-> E  ;
    E -.step_4.-> B  ;
    B -.step_5.-> A ;

上图一键说的很明白了 (你永远也想不到，这个图有多难调QwQ) \[2^1 \times 2^1 = 2^2 等等\]

让我们测试一下，看看

\(eg:\) $2^{10} $

1
2
3
24
--------------------------------
Process exited after 0.4149 seconds with return value 0

\(\qquad \quad \; \: \; 3^{11}\)

1
2
3
177147
--------------------------------
Process exited after 0.4981 seconds with return value 0

取个模再来一次 \(\qquad \quad \, \, \, 3^{99999999}\)

1
2
3
4
3 的 99999999 次方  模数: 1000
667
--------------------------------
Process exited after 0.4642 seconds with return value 0
我们能看出来，一但数一大，递归和循环的效率就有云泥之别了

观摩代码，学习精进

以下代码皆来自洛谷参加代码公开的用户，侵删
展开

message：$24ms ; 784.00KB ; 295B $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int a,b,p;

int power(int x,int y,int z){
	if(y == 0) return 1;
	long long tmp = power(x,y/2,z)%z;
	return tmp*tmp%z*(y%2?x:1)%z;
}

int main(){
	scanf("%d%d%d",&a,&b,&p);
	printf("%d^%d mod %d=%d",a,b,p,power(a%p,b,p));
	
	return 0;
}
展开

message：$24ms ; 808.00KB ; 343B $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a,b,p;
int qp(int x,int y){
	if(y==1)return x;
	if(x==0)return 0;
	if(y==1)return 1;
	ll tmp=qp(x,y/2);
	ll ans=tmp*tmp;
	ans%=p; 
	if(y%2==1)ans*=x;ans%=p;
	return ans;
}
int main(){
	cin>>a>>b>>p;
	cout<<a<<"^"<<b<<" mod "<<p<<"="<<qp(a,b);
	return 0;
}
展开

message：$26ms ; 808.00KB ; 260B $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int a, b, mod;

ll qpow(ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}

int main() {
    cin >> a >> b >> mod;
    cout << a << '^' << b << " mod " << mod << '=' << qpow(a, b) << '\n';
}
🍂全文完↩︎