-
Notifications
You must be signed in to change notification settings - Fork 0
/
power.cpp
executable file
·77 lines (65 loc) · 1.11 KB
/
power.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
using namespace std;
//b->b/2->b/4->b/8->b/16.........1 or 0
int power(int a,int b){
if(b==0){
return 1;
}
if(b==1){
return a;
}
if(b%2==0){
return power(a*a,b/2);
}else{
int ans = power(a*a,(b-1)/2);
return ans*a;
}
}
long long powerMod(long long a,long long b,int MOD){
if(b==0){
return 1;
}
if(b%2==0){
return powerMod((a*a)%MOD,b/2,MOD);
}else{
long long ans = powerMod((a*a)%MOD,b/2,MOD);
return ((a%MOD)*ans)%MOD;
}
}
long long powerModIter(long long a,long long b,int MOD){
long long ans =1;
while(b>0){
int c = b;
//cout<<b<<" ";
if(c&1 == 1){
ans = (ans*a)%MOD;
//cout<<c;
}
a = (a*a)%MOD;
b = b/2;
}
//cout<<" "<<b;
return ans;
}
void helper(int x,int n,int &ans){
if(n==0){
return;
}
ans = ans*x;
helper(x,n-1,ans);
}
int main(){
//x^n 2^3=8
long long x;
cin>>x;
long n;
cin>>n;
int ans=1;
//helper(x,n,ans);
int MOD = 1000000007;
cout<<powerMod(x,n,MOD)<<endl;
cout<<powerModIter(x,n,MOD)<<endl;
cout<<power(x,n);
//cout<<ans;
return 0;
}