[C++] Fast multiply algorythm (BAEKJOON 1629)

Algorithm Quiz

백준 1629 "Multiply"

https://www.acmicpc.net/problem/1629

Get A^B

But the number could be too huge, so devide it by c and get the remainder.

so, get A^B%C

/////////////////////////////////////////////////////////////////////////////////////////////////////

We can solve it with Divide And Conquer.

Use long long type because the number can be a big number.

/* Wrong answer. It could happen overflow. */

#include <iostream>

#include <Windows.h>

using namespace std;

long long a, b, c;

long long calc(long long a, long long b, long long c)

{

if (b == 0) { return 1; }

else if (b == 1) { return a%c; }

else if (b % 2 == 0) { return calc(a*a, b >> 1, c) % c; }

else { return a * calc(a, b - 1, c) % c; }

}

int main() {

cin >> a >> b >> c;

cout << calc(a, b, c) << '\n';

system("pause");

return 0;

} 

/* Correct answer */

#include <iostream>

using namespace std;

long long a, b, c;

long long calc(long long a, long long b, long long c)

{

if (b == 0) {return 1;}

else if(b == 1) {return a%c;}

else if (b % 2 == 0) {long long temp = calc(a, b/2, c); return (temp*temp)%c;}

else {return a * calc(a, b-1, c) % c;}

}

int main() {

cin >> a >> b>> c;

cout << calc(a, b, c) << '\n';

return 0;

}

//
Reference
C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 1629번:곱셈 답
http://codecollector.tistory.com/m/268