[BOJ 알고리즘, C++]#1629_곱셈, 거듭 제곱의 특성, 지수 법칙

2024. 7. 30. 19:29· 카테고리 없음
목차
  1. #1. 문제
  2. #2. 풀이
  3. 1. 지수 법칙
  4. 2. 거듭제곱의 특징
  5. 3. 거듭 제곱의 특징을 활용하여 분할-정복 설계!
  6. #3. 코드

#1. 문제

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

 


 

#2. 풀이

 

1. 지수 법칙

(A^n)^m = A^(m*n)

 

2. 거듭제곱의 특징

1. n이 짝수일 경우: Aⁿ = (A^(n/2))²
2. n이 홀수일 경우: Aⁿ = A * (A^(n-1))

 

3. 거듭 제곱의 특징을 활용하여 분할-정복 설계!

  1. 먼저, 분할-정복을 설계합니다. B를 2로 나눈 값을 다시 B로 설정하여 분할 작업을 먼저 수행합니다. 분할 작업 수행을 위해 기저 조건으로 B가 1 혹은 0이 되었을 경우 결과 값을 반환하는 것만 설정해 주고, 기본적인 종료 조건보다 재귀 호출을 먼저 작성해 줍니다.
  2. 다음으로, 재귀호출의 반환 값(현재 B가 1/2일 때, 결과 값)을 제곱해 주고 그 결과 값을 C로 나눈 나머지 값을 먼저 구해줍니다.
  3. 그리고, B가 짝수일 경우에 위 결과 값을 그대로 반환합니다. 반대로, 홀수일 경우, 위 결과 값에 A를 추가적으로 곱해주고 다시 C로 나눈 나머지 값을 반환합니다.

 


 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/1629
*   @문제: A를 B번 곱한 수를 C로 나눈 너머지
*   @설명
        1. 지수 법칙: (A^n)^m = A^(m*n)
        2. 거듭 제곱의 특성, 아니 이걸 어떻게 알아...
        - B가 짝수일 경우, Aⁿ = (A^(N/2))²
        - B가 홀수일 경우, Aⁿ = A * (A^(B-1))
        3. 예제, A = 3, B = 13, C = 17
        1.B가 홀수일 경우
            3^13 = 3 * (3^(13-1))
            3^13 = 3 * (3^(13-1)) = 3 * (3^12)
            B가 짝수로 바뀌었다.
            3^13 = 3 * (3^(13-1)) = 3 * (3^12) = 3 * (3^(12/2)^2) = 3 * 3^6 * 3^6
                                                    |    분할    |
            결과적으로, B를 2로 나눈 값으로 분할 및 재귀 호출 진행 가능하다. 
        2.B가 짝수일 경우
            3^12 = 3^(12/2)^2
            3^12 = 3^(12/2)^2 = 3^6 * 3^6
                  |   분할   |
            역시, B를 2로 나눈 값으로 분할 및 재귀 호출 진행이 가능해 보인다.
        3. 기저 조건 설정, 하위 문제에서 B가 1이되면 바로 A&C를 반환하도록 설정
        4. 재귀 호출 수행하고, 그 반환 값은 현재 B값을 2로 나눈값으로 구한 한 쪽의 값(만약, B가 6이라면, 하위 문제로부터 전달 받은 값은 3^6이다.)
           따라서, 전달 받은 값이 tmp라면, (tmp * tmp)%C 해주고, B가 짝수라면 그대로 반환, 반대로 홀수라면 A를 추가적으로 곱해주어 반환한다.
*/


#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;

ll A, B, C;

ll solve(ll a, ll b, ll c)
{
    if(b==0) return 1;
    if(b==1) return a%c;

    ll tmp = solve(a, b/2, c);
    tmp = (tmp*tmp)%c; // 중간 값 계산 중요! 홀수의 경우 (a*(tmp*tmp))%c 는 tmp가 충분히 큰 상태에서 오버플로우 발생 위험, 따라서 미리 c로 모듈러 연산 수행

    //@짝수
    if(b%2 == 0) return tmp;
    else return (a*tmp)%c;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> A >> B >> C;

    cout << solve(A, B, C);

    return 0;
}

 


 

 

 

 

저작자표시 (새창열림)
  1. #1. 문제
  2. #2. 풀이
  3. 1. 지수 법칙
  4. 2. 거듭제곱의 특징
  5. 3. 거듭 제곱의 특징을 활용하여 분할-정복 설계!
  6. #3. 코드
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • DP
  • Effective C++
  • dfs
  • 우선순위 큐
  • 디자인 패턴
  • 정렬
  • unreal
  • 개발
  • 그래프
  • BFS
  • 알고리즘
  • set
  • stl
  • Unreal Blueprint
  • programmers
  • C++
  • BOJ
  • 기술 질문
  • 트리
  • 최단 경로

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ 알고리즘, C++]#1629_곱셈, 거듭 제곱의 특성, 지수 법칙
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.