[5615] 아파트 임대

문제 링크 : https://www.acmicpc.net/problem/5615

5615 - 아파트 임대

본문

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

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

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

입력

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

출력

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

제한

시간 제한	메모리 제한
1sec	256MB

---

풀이

구하려는 것은 입력하는 수가 양의 정수 $x, y$에 대해 $2xy+x+y$의 꼴로 만들어질 수 있는가를 확인하는 것이다. 아무리 봐도 그냥 수수께끼를 가장한 수학 문제 같다.

$2xy+x+y=k$라고 하자. 그러면 입력되는 숫자 $n$이 $k$를 대체할 수 있는지 확인하면 될 것이다. 더하기가 있으면 계산이 힘드므로 식을 정리해보자.

\[\begin{align} k &= 2xy + x + y = x(2y + 1) + y \end{align}\]

아직 더하기가 있다. 저 $+y$를 제거할 방법을 찾아야한다. 가만 보면 옆에 $(2y+1)$이 보이므로, $+y$를 $2y+1$로 바꿀 수 있는 방법을 찾아보면 아래의 방법이 있다.

\[\begin{align} 2k + 1 &= 4xy + 2x + 2y + 1 = 2x(2y + 1) + 2y + 1\\ &= (2x+1)(2y+1) \end{align}\]

$x, y$는 양의 정수이므로, $2k+1$은 1을 제외한 두 홀수의 곱으로 표현되는 홀수라는 것을 알 수 있다. 그리고, 그것은 곧 “$2k+1$이 소수가 아니다”는 조건이 된다는 것을 눈치챌 수 있다. 그래서 주어지는 숫자 $n$에 대하여 $2n+1$이 소수인지 아닌지 판별하는 문제로 바꿔 생각할 수 있게 된다.

소수 판별법은 기존에 알던 방법을 사용하면 될 것 같지만, 숫자의 범위가 골때린다. 입력으로 주어질 수 있는 $n$의 최댓값이 $2^{31}-1$이다. 즉 우리가 구하려는 $2n+1$의 최댓값은 $2^{62}-1$이다. long long의 범위 끝까지 간다고 보는게 맞을 것 같다. 그래서 기존의 $O(\sqrt{n})$ 방법으로는 답을 찾을 수 없다.

그래서 찾아본 것이 밀러-라빈 소수판별법이다. 설명은 참고. 이 방법을 이용하면 큰 수의 범위의 소수도 빠른 시간 내에 판별할 수 있다고 한다.

문제의 정답은, 입력으로 주어지는 숫자 $n$에 대해 $2n+1$이 소수인지 판별하고, 소수의 개수만 세어주면 된다. 사실상 큰 수의 소수 판별법을 연습하는 문제 느낌인 것.

• 참고 알고리즘 : 밀러-라빈 소수판별법

코드

사용 언어 : C

최종 수정일 : 2023 / 4 / 14

#include <stdio.h>

typedef unsigned long long ll;
typedef char bool;
const bool true = 1;
const bool false = 0;

ll base[3] = {2, 7, 61};
int base_len = 3;

ll power(ll x, ll y, ll m) {
    ll res = 1;
    x %= m;

    while (y > 0) {
        if (y % 2 == 1) {
            res = (res * x) % m;
        }

        y /= 2;
        x = (x * x) % m;
    }

    return res;
}

bool miller(ll n, ll a) {
    if (a % n == 0) {
        return true;
    }

    ll d = n - 1;
    while (true) {
        ll temp = power(a, d, n);
        if (temp == n - 1) {
            return true;
        }
        if (d % 2 == 1) {
            return (temp == 1 || temp == n - 1);
        }
        d /= 2;
    }
}

bool isPrime(ll x) {
    ll result = true;
    for (int i = 0; i < base_len; ++i) {
        result &= miller(x, base[i]);
    }
    return result;
}

int main() {
    int n;
    scanf("%d", &n);

    int result = 0;
    for (int i = 0; i < n; ++i) {
        ll x;
        scanf("%lld", &x);

        if (isPrime(2 * x + 1) == true) {
            ++result;
        }
    }

    printf("%d", result);
    return 0;
}