알고리즘 - Python / 백준 - 5615번 : 아파트 임대

5615번: 아파트 임대 (acmicpc.net)

5615번: 아파트 임대

 

---

풀이

• 아파트의 면적이 2xy + x + y 일때 , ( x , y는 양의 정수 ) 면적이 될 수 없는 값을 구하는 문제이다.
• 식을 정리하면 2S + 1 = (2x + 1)(2y + 1) 이므로 , 두 홀수의 곱으로 다른 홀수를 만들 수 있는지 없는지 판단하는 문제이다. 따라서 2S + 1 이라는 홀수가 소수인지 아닌지 판별하는 문제이다.
• S의 범위가 매우 크므로 , 일반적인 소수 알고리즘이 아닌 "밀러-라빈 소수 판별법"을 사용한다.
• 밀러-라빈 소수 판별법의 a를 2,7,61을 가지고 커버가 될 줄 알았지만 틀렸다고 나와 이후의 a 사용값인 2,3,5,7,11을 사용하였다.
• 밀러-라빈 소수 판별법 알고리즘에 대해서는 아래 위키백과를 참고하자.

 

밀러-라빈 소수판별법 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

밀러-라빈 소수판별법 - 위키백과, 우리 모두의 백과사전

 

def powmod(a,b,m):
    result = 1
    while b > 0:
        if b % 2 != 0:
            result = (result * a) % m
        b //= 2
        a = (a * a) % m

    return result

def mr(n,a):
    r = 0
    d = n-1
    while (d%2 == 0):
        r += 1
        d = d // 2
    x = powmod(a,d,n)
    if x == 1 or x == n-1:
        return True
    for i in range(0,r-1):
        x = powmod(x,2,n)
        if x == n-1:
            return True
    return False

import sys
ans = 0
m = int(sys.stdin.readline())
for i in range(m):
    k = int(sys.stdin.readline())
    check = 0
    for i in [2, 3,5,7,11]:
        if mr(2*k+1,i) == False:
            break
        else:
            check += 1
    if check == 5:
        ans += 1
print(ans)

---