티스토리 뷰

PS/백준

[백준/C++] 1629번 - 곱셈

unside 2021. 3. 18. 19:47

오늘의 문제!

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

입력

첫째 줄에 A B C가 주어짐

풀이

(A x B) % C 는 ((A%C) * (B%C)) % C 와 같다

그리고 B가 짝수이면 A의 B제곱은 A의 B/2제곱의 2제곱으로 나타낼 수 있다. B가 홀수 이면 A의 B/2제곱의 2제곱에 A를 곱한게 A의 B제곱이 된다.

이때 주의 점은 A B C가 최대 2,147,483,647 이므로 자료형 선택에 있어 조심해야한다.
A가 20억 B가 2일때 C가 21억이면 결과를 구하는 과정에서 A * A가 400억이 되어 int 를 사용하면 중간과정에서 오버플로우가 발생한다.

소스

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
 
#include <stdio.h>
#include <iostream>
using namespace std;
 
long long cal(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 == 1){
        return ((((cal(A,B/2,C)%C) * (cal(A,B/2,C)%C)) % C)*(A%C)) % C;
    }
    else{
        return ((cal(A,B/2,C)%C) * (cal(A,B/2,C)%C)) % C ;
    }
}
 
int main(void){
    long long A,B,C;
    cin >> A >> B >> C;
    cout << cal(A,B,C);
    return 0;
}
 
cs
저작자표시 비영리 동일조건

'PS > 백준' 카테고리의 다른 글

[백준/C++] 1725번 - 히스토그램  (0) 2021.03.20
[백준/C++] 2104번 - 부분배열 고르기  (0) 2021.03.19
[백준/C++] 1493번 - 박스 채우기  (0) 2021.03.17
[백준/C++] 15748번 - Rest Stops  (0) 2021.03.12
[백준/C++]13904번 - 과제  (0) 2021.03.11
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/02   »
일 월 화 수 목 금 토
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
글 보관함