[백준 5615] 아파트 임대 [C]

동규부동산에서 아파트를 임대하고 있다. 아파트의 방은 아래 그림과 같이 면적이 2xy + x + y이다. (x와 y는 양의 정수)

동규부동산의 카탈로그에는 아파트의 면적이 오름차순으로 적혀져 있지만, 이 중 일부는 있을 수 없는 크기의 아파트이다. 만약, 이런 크기의 아파트를 임대하겠다고 말하면, 동규는 꽝! 이라고 외치면서, 수수료만 떼어간다.

동규부동산의 카탈로그에 적힌 아파트의 면적이 주어졌을 때, 있을 수 없는 크기의 아파트의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 2^31-1이하인 양의 정수이다.

출력

첫째 줄에 있을 수 없는 아파트 면적의 수를 출력한다.

---

풀이

2xy + x + y = area라고 할 때, 모든 x와 y를 대입하면 시간초과가 발생한다.

Miller-Rabin 소수 판별법을 사용해 2area + 1이 소수가 아닌지 판단하는 문제다.

 

x와 y가 양의정수이기 입력받은 면적을 다음과 같이 이용할 수 있다.

4xy + 2x + 2y + 1 = 2area + 1,

(2x+1)(2y+1) = 2area + 1일 때,

2area + 1이 소수면 (2x+1), (2y+1)이 각각 1, 2area + 1이 되어야 한다.

이 때

2x + 1 = 1, x = 0이므로 불가능한 면적이다.

 

 

입력받는 수가 2^31 - 1이므로 2, 7, 61에 대해서만 Miller-Rabin 소수 판별법을 사용해도 충분하다.

---

소스코드

#include <stdio.h>
#define ui unsigned int
#define ull unsigned long long
int a_list[3] = {2, 7, 61};
ui pow(ull a, ui b, ui mod){
    ull result = 1;
    while (b){
        if (b & 1) result = result*a %mod;
        b >>= 1;
        a = a*a %mod;
    }
    return result;
}
int miller_rabin(ui n, int a){
    if (a%n == 0) return 1;
    ui d = n - 1;
    while (d % 2 == 0){
        if (pow(a, d, n) == n-1)
            return 1;
        d /= 2;
    }
    ui temp = pow(a, d, n);
    return temp == 1 || temp == n-1;
}
int prime(ui n){
    for (int i = 0; i < 3; i++)
        if (!miller_rabin(n, a_list[i]))
            return 0;
    return 1;
}
int main(){
    int N, cnt = 0;
    scanf("%d", &N);
    while (N--){
        ui val;
        scanf("%u", &val);
        if (prime(2*val + 1)) cnt++;
    }
    printf("%d", cnt);
}

---

출처 및 참고자료

5615번: 아파트 임대

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

Miller–Rabin primality test - Wikipedia