BOJ 5615 아파트 임대[C++]

먼저 문제에서 주어진 식을 변형해야 한다.

 

 

아파트의 면적을 n이라 놓으면

2xy + x + y = n.

 

양변에 2를 곱하고 1을 더하면

4xy + 2x + 2y + 1 = 2n + 1.

 

좌변을 인수분해하면

(2x + 1)(2y + 1) = 2n + 1.

문제에서는 불가능한 아파트 면적을 찾는 것이다. x,y의 조건에서 2x+1, 2y+1모두 3이상의 홀수이고

이때 가능한 2n + 1 값은 3이상의 홀수 두개로 소인수분해된다.

 

즉 불가능한 2n + 1값은 3이상의 홀수 두개로 소인수분해 되지 않는 수인데, 

2x + 1 과 2y + 1은 짝수가 나올 수 없으므로 둘 중 하나가 3보다 작은 홀수, 즉 1이다.

따라서 2n +1 의 값이 1 x (1이 아닌 홀수) 로만 인수분해 할 수 있는 수 즉 소수가 될때,

이를 만족하는 양의 정수 n값은 존재하지 않게 되는 것이다. 

 

즉 문제를 요약하면 아파트 면적 n에 대해 2n + 1이 소수인 것의 개수를 세서 출력하면 되는 것이다.

 

따라서 소수 판별 알고리즘을 사용해야 하는데, 소수 판별 알고리즘 중 가장 유명한 것은 에라토스테네스의 체이다.

최적화된 에라토스테네스 체의 시간복잡도는 N * log (log N)으로 판별하려는 소수의 최대값인 2^32 - 1 을 대입하면 시간초과가 날 것이다. (100,000개의 쿼리에 대해 각각 소수판별을 해도 시간초과가 날 것이다.)

 

그래서 더욱 빠른 소수판별 알고리즘인 밀러 라빈 소수 판별법을 적용해야한다.

밀러 라빈 소수 판별법의 시간복잡도는 O(log^3 N)에 불과해 시간내에 소인수분해가 가능하다.

밀러-라빈 소수판별법에 관한 이론과 자세한 내용은 아래를 참고해서 공부했다.

 

https://goodbyefin.tistory.com/47 

https://rebro.kr/46

소수 판별법 - 에라토스테네스의 체, 밀러-라빈(Miller-Rabin) 소수판별법

밀러 - 라빈 소수 판별법 (Miller - Rabin primality test)

 

아래는 밀러-라빈 소수판별법을 사용해 AC를 받은 코드이다.

#include <bits/stdc++.h>
#define ulld unsigned long long int

using namespace std;



ulld fastPow(ulld a, ulld b, ulld mod) {

    ulld ret = 1;
    a %= mod;

    while (b) {
        if (b % 2) ret = (ret * a) % mod;
        b /= 2;
        a = (a * a) % mod;
    }

    return ret;
}



bool isPrime(ulld num, ulld test) {
    if (test % num == 0) return true;

    ulld s = num - 1;

    while (true) {
        ulld temp = fastPow(test, s, num);
        if (temp == num - 1) return true;
        if (s % 2) return (temp == 1 || temp == num - 1);
        s /= 2;
    }

}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n, cnt = 0;
    ulld buf;
    vector<ulld> tests = {2,7,61};

    cin >> n;

    while (n--) {
        cin >> buf;
        buf = 2 * buf + 1;

        
        int i = 0;
        while (true) {
            
            if (i == tests.size()) {
                cnt++;
                break;
            }
            if (! isPrime(buf, tests[i]))
                break;
            i++;
        }
    }

    cout << cnt;



    return 0;
}

 

long long int가 아닌 unsigned long long int를 사용했다.

long long int를 쓰면 5%정도에서 틀렸습니다가 나온다.

 

overflow나는 부분은 실험해보진 않았지만 fastPow함수 내부인 것 같다.

mod로 들어올 수 있는 수의 범위는 2^32 - 1 이하이다.(2n + 1)

그런데 아래에서 a는 mod로 나눈 나머지 값이므로 mod 미만이다.

그런 수 a를 제곱하는데, 그 최댓값은 (2^32 -2)^2  는 long long int의 범위인 2^63 - 1을 넘어설 수 있다.

따라서 계산 중 overflow가 발생할 수 있어 unsinged long long int를 사용해야한다.