수학2_a^b에대해서 알아보자.

a^b

• a의 b제곱을 빠르게 구해야함

int ans = 1;
for (int i=1; i<=b; i++){
	ans = ans *a;
}

• 이렇게 하면 직관적이지만 O(b)라는 시간이 걸림

분할 정복을 이용하는 방법

• a^2b = a^b * a^b
• a^(2b+1) = a * a^2b
  • 이렇게 하면됨

int calc (int a, int b){
	if(b==0) reutrn 1;
	else if(b==1) return a;
	else if(b%2==0){
		int temp = clac(a,b/2);
		return temp * temp;
	}
	else return a * clac(a, b-1); //b%2==1;
}

• 이진수 원리를 이용하는 경우

int calc(int a, int b){
	int ans = 1;
	while(b>0){
		if(b%2==1) ans*=a;
		a = a * a;
		b /=2;
	}
	return ans;
}

• 이진수의 원리 왜? 이렇게 하지?
  • 예를 들어 3의 27승인 경우
    • 27은 이진수로 11011인데
    • 2^0 + 2^1 + 2^2 + 2^3 + 2^4 인데
    • = 1 + 2 + 8 + 16
    • 즉, 3^27 = 3^(1+2+8+16)
    • 3^1 * 3^2 * 3^8 * 3^16
      • 그렇기 때문에 a를 a*a로 곱해가면서 제곱을 구하게 됨

곱셈

• 문제 링크
  • https://www.acmicpc.net/problem/1629
• 문제 풀이
  • 위의 내용을 적용하면된다.
• 소스코드
• 분할정복을 이용한 방법

#include<iostream>
using namespace std;

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

int main(void) {
	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long long A, B, C;
	cin >> A >> B >> C;
	int result = calc(A, B,C);
	cout << result % C << '\\n';
	return 0;
}

• 이진법을 이용한 방법