728x90 밀러-라빈 소수판별법1 [python] 백준 5615 아파트 임대 https://www.acmicpc.net/problem/5615 5615번: 아파트 임대 첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다. www.acmicpc.net 문제해결 2xy+x+y로 무엇을 할 수 있을지 생각하면 아무것도 할 수 없다.(1차 고비) 인수분해를 해야할 것 같은데 S = 2xy+x+y라 할 때 2S+1 = (2x+1)(2y+1)로 인수분해 할 수 있다. 2S+1은 두 홀 수의 곱으로 나타낼 수 있는 것이다. 그럼 이것을 왜 하는 것인가? 바로 2S+1이 소수인지 판별해서 S를 판별하면 되는 것이다. 2S+1이 소수인지 판별하는 것은 밀러-라빈 소수 .. 2023. 7. 31. 이전 1 다음 728x90