백준 1629 곱셈 C++

백준 1629 곱셈.

백준 1629번 "곱셈" 문제의 자세한 내용은 글 하단의 문제 링크를 참고하세요.

1629 문제에 주어지는 입력 및 예시

입력: 

10 11 12

출력:

4

코드

백준 1629번 "곱셈" 문제의 코드입니다.

#include <bits/stdc++.h>
using namespace std;
long long c;
long long calc(long long a, long long b){
	if(b==1) return a%c;
	long long result=calc(a, b/2);
	//(a*b)%c==(a%c*b%c)%c
	return result=(result*result)%c*(b%2==1?a:1)%c;
}
int main(){
	long long A,B;
	cin>>A>>B>>c;
	cout<<calc(A,B);
	return 0;
}

 

실행

위의 코드를 예제의 입력을 넣어 실행했을 때의 결과입니다.

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

1629번: 곱셈