[python] 백준 5615 아파트 임대

https://www.acmicpc.net/problem/5615

5615번: 아파트 임대

 

문제해결

• 2xy+x+y로 무엇을 할 수 있을지 생각하면 아무것도 할 수 없다.(1차 고비)
• 인수분해를 해야할 것 같은데 S = 2xy+x+y라 할 때 2S+1 = (2x+1)(2y+1)로 인수분해 할 수 있다.
• 2S+1은 두 홀 수의 곱으로 나타낼 수 있는 것이다.
• 그럼 이것을 왜 하는 것인가? 바로 2S+1이 소수인지 판별해서 S를 판별하면 되는 것이다.
• 2S+1이 소수인지 판별하는 것은 밀러-라빈 소수 판별법을 이용하면 된다.
• x,y가 양의 정수이면 S≥4이므로 S=1,2,3일때는 x,y,를 구할 수 없다.
• S≥4일 경우의 수는 밀러-라빈 소수 판별법 이용한다.

https://ko.wikipedia.org/wiki/%EB%B0%80%EB%9F%AC-%EB%9D%BC%EB%B9%88_%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95

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

 

 

CODE

import sys
input = sys.stdin.readline

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 MillerRabin(n,a):
    r = 0
    d = n-1
    while(d%2==0):
        r += 1
        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
if __name__=='__main__':
    ans = 0
    n = int(input())
    for _ in range(n):
        k = int(input())
        cnt = 0
        if k<4:
            ans+=1
            continue
        for i in [2,3,5,7,11]:
            if MillerRabin(2*k+1,i)==False: #2*k+1을 두 홀수의 곱으로 나타낼수 있는지 판볋
                break
            else:
                cnt+= 1
        if cnt==5:
            ans+=1
    print(ans)