題敘
http://domen111.github.io/UVa-Easy-Viewer/?374
給定三個整數 $B$ $P$ $M$ ，求 $B^P mod M$
想法1 - 暴力解
從 $1$ 開始到 $P$ ，每次乘上 $B$ 再模 $M$ ，複雜度 $O(P)$
但是複雜度過高，會TLE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
ll b,p,m;
int main(){
while(cin>>b>>p>>m){
ll ans=1;
for(int i=1 ; i<=p ; i++){
ans = ans*b % m;
}
cout<<ans<<"\n";
}
return 0;
}
|
想法2 - 快速冪
觀察我們計算的過程
如果我們要計算 $2^4$ ，我們會直接把 $2$ 乘 $4$ 次
但是實際上發現 $2^4 = (2^2)^2$
所以對於次數是偶數的，可以只計算一次，再來平方即可
而奇數呢?
假如我們要計算的 $3^3$
實際上會等同於 $3 * 3^2$
這樣一來一定能轉換成一次乘上偶數次
複雜度 $O(log_2 P)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
ll b,p,m;
ll solve(int x,int y,int mod){
if(y==0)
return 1;
if(y%2)
return (x*solve(x,y-1,mod))%mod;
else{
ll half=solve(x,y/2,mod);
return (half*half)%mod;
}
}
int main(){
while(cin>>b>>p>>m){
cout<<solve(b,p,m)<<"\n";
}
return 0;
}
|