밀러-라빈 소수 판정법1 [백준 5615] 아파트 임대 (Feat. 밀러-라빈 소수 판정법) (Platinum I) https://www.acmicpc.net/problem/5615 5615번: 아파트 임대 첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다. www.acmicpc.net 매우 자명한 어떤 절차에 의해, 2N + 1이 소수가 되는 N을 찾는 문제임을 알 수 있다. Naive한 소수 판별을 짜면 시간복잡도 \(O(T \sqrt{N})\)이 나와서 TLE가 난다. 시간복잡도를 줄일 수 있는 방법으로 밀러-라빈 소수 판정법을 이용하자. a = 2, 7, 61에 대하여 \( n - 1 = 2^s d \)로 놓는다. \( a^d \ne 1 \mod n \)이고, 모든 r : 0 ~ s.. 2022. 8. 28. 이전 1 다음
