본문 바로가기

분할 정복을 이용한 거듭제곱/정수 거듭제곱

 (44)
백준 4233번: 가짜소수 https://www.acmicpc.net/problem/4233 4233번: 가짜소수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, p와 a를 포함하고 있다. 입력의 마지막 줄에는 "0 0"이 주어진다. (2 < p ≤ 1,000,000,000, 1 < a < p) www.acmicpc.net 본문에서 페르마의 소정리를 친절하게 설명해주고 있습니다. 그러나 예제 출력을 잘 보면 알 수 있듯이, 어떤 수 p가 밑 a에 대해 페르마의 소정리를 만족하더라도 가짜소수가 아닐 수 있습니다. 따라서, p가 밑 a에 대해 페르마의 소정리를 만족하는지 확인한 후, 만약 만족한다면 p가 "소수"인지 아닌지를 판별하면 됩니다. 본문에 나와있듯이 p가 최대 $10^{9}$ ..
백준 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}..

티스토리툴바