BOJ 1629 (곱셈)

• 문제
  자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
  
  
• 입력
  첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
  
  
• 출력
  첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

#include<iostream>
using namespace std;
long long A, B, C;
long long answer;
void fast_io() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

void input() {
	cin >> A >> B >> C;
}

long long solve(long long exponent) {
	if (exponent == 0) {
		return 1;
	}
	else if (exponent == 1) {
		return A % C;
	}
	else {
		long long temp = solve(exponent / 2) % C;
		if (exponent % 2 == 0) {
			return temp * temp % C;
		}
		else {
			return temp * temp % C * A % C;
		}
	}
}

int main() {
	fast_io();
	input();
	cout << solve(B);
	return 0;
}

   입력의 최대크기가 21억이기 때문에 O(N)이상의 시간복잡도를 가진 알고리즘을 짜면 시간초과가 난다. 시간복잡도를 줄이기 위해 a^2n= a^n * a^n 과 같이 나누어 계산하는 방법을 이용하여 O(logN)의 시간복잡도로 줄일 수 있다.

다만 위와 같이 나누는 식은 지수부분이 짝수일 때만 가능하고 홀수일 때는 A%C를 곱해주면 된다.

시간 복잡도 : O(logN)

숏코딩 1

#import<iostream>
long long i,n,k,M,R=1;main()
{std::cin>>n>>k>>M;while(k>0){if(k&1){R*=n;R%=M;}n=n*n%M;k>>=1;}std::cout<<R;}

   비트연산자를 이용한 풀이인데 이해하기 어렵다..

숏코딩 2

#include <iostream>
using namespace std;

int main(){
	long long a, b, c, res = 1;
	cin >> a >> b >> c;
	while(b){
		if (b%2)  res = (res*a)%c;
		a = (a*a)%c, b /= 2;
	}
	cout << res;
}