본문 바로가기

전체 글

 (116)
백준 11819번: The Shortest does not Mean the Simplest www.acmicpc.net/problem/11819 11819번: The Shortest does not Mean the Simplest The only line of the input file contains three integers: A, B, C (1 ≤ A,B,C ≤ 1018). Numbers are separated by spaces. www.acmicpc.net 이전에 올렸던 1629, 13171번과 거의 같은 문제입니다. 2021/01/23 - [분할 정복을 이용한 거듭제곱/정수 거듭제곱] - 백준 1629번: 곱셈 2021/01/23 - [분할 정복을 이용한 거듭제곱/정수 거듭제곱] - 백준 13171번: A 따라서 코드도 거의 같습니다. #include long long add_mod..
백준 1629번: 곱셈 www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 구하는 것이 이전 글과 같습니다. 2021/01/23 - [분할 정복을 이용한 거듭제곱/정수 거듭제곱] - 백준 13171번: A 백준 13171번: A www.acmicpc.net/problem/13171 13171번: A 음이 아닌 두 정수 A, X 가 있을 때 AX을 구하는 방법을 생각해보자. 물론 이 수는 매우 클 수 있기에, 1,000,000,007 (= 109 + 7)로 나눈 나머지를 구할 것이다. a mod.. memoacmicpc.tistory.com 저는 A,..
백준 13171번: A www.acmicpc.net/problem/13171 13171번: A 음이 아닌 두 정수 A, X 가 있을 때 AX을 구하는 방법을 생각해보자. 물론 이 수는 매우 클 수 있기에, 1,000,000,007 (= 109 + 7)로 나눈 나머지를 구할 것이다. a mod x를 a를 x로 나눴을 때의 나머지라고 표 www.acmicpc.net 본문에 Binary Exponentiation의 원리가 잘 설명되어있습니다. $A^{X} \left ( mod \left ( 10^{9} + 7 \right ) \right )$ 을 잘 구해주면 됩니다. 다음 링크에 있는 함수만 사용하였습니다. 2021/01/23 - [분할 정복을 이용한 거듭제곱] - 기본 이론 기본 이론 큰 자연수 A, B, C에 대해 $ A^{B}..
기본 이론 큰 자연수 A, B, M에 대해 $ A^{B}\left ( mod M \right ) $의 값을 필요로 하는 문제가 많습니다. 이 카테고리에서는 이런 문제를 몇 가지 풀어보려고 합니다. 이 글에서는 문제를 풀기 이전에 주요 개념을 간략하게 설명해보도록 하겠습니다. 1. Exponentiation By Squaring $x^{y}$를 분할 정복을 이용하여 빠르게 구하는 기법입니다. 이때 y의 이진수 꼴을 쓰는 경우 Binary Exponentiation이라고도 합니다. 실제 코드 전에 간단히 예시를 보겠습니다. (10^13) = (10^8) * (10^4) * (10^1) 13 = 1101 8 = 1000 4 = 0100 1 = 0001 구조가 보이나요? $x^{y}$에서 y를 binary로 나타낸 것을 ..

티스토리툴바