알고리즘/알고리즘 이론, 템플릿
분할 정복을 이용한 거듭제곱
b1ackhand
2023. 7. 17. 19:54
ll pow(ll a, ll p)
{
ll ret = 1;
while (p > 0)
{
if (p & 1)
ret = ret * a;
a = a * a;
p >>= 1;
}
return ret;
}
재귀
#include<iostream>
using namespace std;
long long A, B, C;
long long divide(long long a, long long b, long long c)
{
if (b == 1)
{
return a % c;
}
long long tmp = divide(a, b/2, c) % c;
if( b % 2 == 0 )
{
return tmp * tmp % c;
}
else
{
return tmp * tmp % c * a % c;
}
}
int main() {
cin >> A >> B >> C;
cout << divide(A, B, C);
}