💯Problem Solving
[BOJ] 1629 곱셈
date
Jul 11, 2023
slug
boj-1629
author
status
Public
tags
Python
BOJ
summary
백준 1629번 문제풀이입니다.
type
Post
thumbnail
category
💯Problem Solving
updatedAt
Jul 11, 2023 07:55 AM
문제 링크
문제
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
문제풀이
성질 두가지를 사용해야한다,
- 지수 정리
- 나머지 정리
A, B, C = 10, 11, 12로 입력이 들어오면
→ 10^11%12를 구해야한다.
→ A^B%C 형태를 SF라고 정하면
10^11%12를 지수정리를 사용해서 나누면 ( 10^6 * 10^5 ) % 12
( 10^6 * 10^5 ) % 12를 나머지 정리를 통해서 나누면
( (10^6 % 12) * (10^5 % 12) ) % 12 형태가 된다.
(10^6 % 12) = ((10^5 % 12) * (10^1 % 12)) % 12가 되서
재귀 호출을 하는 함수의 배수가 홀수면 A를 추가로 곱해주어 C로 나눠주면 해결가능하다.
이건 (SF * SF) % C가 된다. 즉 SF는 (SF * SF) % C 형태로 재귀할 수 있다는 뜻이고
SF가 구할 수 있는 형태 10^11 % 12 가 될때까지 반복해준후 재귀형태로 구하면 풀 수 있다.
파이썬 문제풀이 코드
A,B,C = tuple(map(int, input().split())) def dq(number, m): if m == 1: return A % C else: tmp = dq(number, m//2) if m % 2 == 0: return (tmp * tmp) % C else: return (tmp * tmp * A) % C print(dq(A, B))
시간복잡도
- logN
입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.