곱셈
문제
자연수 A를 B번 곱한 수를 알고 싶다.
단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다.
A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
1
2
3
4
5
예제 입력 1
10 11 12
예제 출력 1
4
풀이
분할 정복이 익숙하지 않아서 조금 해맸다.
사실상 재귀라고 생각하니까 어떻게 할지 감이 오는 것 같기도 하고
반씩 쪼개는 걸 더 해봐야겠다.
1
return (k * k)%c * a%c;
이 부분을
1
return (k * k * a)%c;
로 했어서 계속 틀렸었는데 a과 굉장히 큰 값이기에 그런 것 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
using namespace std;
long long solve(long long a, long long b, long long c){
if(b==1)return a%c;
long long k = solve(a, b/2, c);
if(b%2==1){
return (k * k)%c * a%c;
}
else{
return (k * k) % c;
}
}
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long a, b, c;
int n, m, t;
char c1, c2, c3;
cin >> a >> b >> c;
long long ans;
ans = solve(a,b,c);
cout << ans%c;
return 0;
}