[백준 5615번] 아파트 임대

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

5615번: 아파트 임대

<참조>

Miller-Rabin

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

 

<문제 풀이> 수학, 정수론, Miller-Rabin(밀러-라빈) 소수 판별법

2xy + x + y = s라고 하고 인수분해 꼴로 만들면 (2x+1)(2y +1) = (2s + 1)이라고 쓸 수 있습니다.

-> (x+1)(y+1)에서 접근

 

x, y가 각각 양의 정수라고 했으므로 (2x+1) >= 3, (2y + 1) >= 3을 만족하므로 2s+1은 3이상의 두 홀수의 곱으로 표현이 되므로 소수의 정의에 의해서 절대 소수가 나올 수 없습니다.

 

따라서 2s + 1이 소수임을 판별하면 됩니다. (소수이면 있을 수 없는 아파트)

 

문제에서 s의 범위가 2^31 -1 이하이므로 2 * s + 1을 일반적인 소수 판별을 하면 시간 초과이므로 Miller-Rabin(밀러-라빈) 소수 판별법을 사용해야 됩니다.

 

<소스 코드>

#include <iostream>
using namespace std;
 
typedef unsigned long long ull;
 
ull power(ull x, ull y, ull p) {
    ull res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1) {
            res = (res * x) % p;
        }
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
bool miller_rabin(ull n, ull a) {
    ull r = 0;
    ull d = n - 1;
    while (d % 2 == 0) {
        r++;
        d = d >> 1;
    }
    ull x = power(a, d, n);
    if (x == 1 || x == n - 1) return true;
    for (int i = 0; i < r - 1; i++) {
        x = power(x, 2, n);
        if (x == n - 1) return true;
    }
    return false;
    
 
}
 
bool isPrime(ull n) {
    ull alist[5] = { 2, 3, 5, 7, 11 };
    if (n <= 1) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;
    for (int i = 0; i < 5; i++) {
        ull a = alist[i];
        if (n == a) return true;
        if (!miller_rabin(n, a)) return false;
    }
    return true;
 
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, cnt = 0;
    cin >> n;
    while (n--) {
        ull s;
        cin >> s;
        if(isPrime(2*s+1)) cnt++;
    }
    cout <<cnt;
    return 0;
}