BOJ 5615

문제

아파트 임대 성공다국어

문제

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

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

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

입력

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

출력

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

풀이

2xy + x + y  = S 라 했을때, (2x+1)(2y+1) = 2S+1로 나타낼 수 있다. x, y의 범위가 양의 정수이므로 2S+1은 무조건 합성수이다. 그러므로 입력받은 S에 대해서 2S+1이 소수인 경우, 정답 카운트를 하나 올려주면 된다.

 

#include <iostream>
using namespace std;
#define ll unsigned long long 
ll N, ans;
int a_param[5] = {2, 3, 5, 7, 11};
ll power(ll x, ll y, ll mod) {
    ll result = 1;
    x %= mod;
    while(y) {
        if(y%2) result = (result*x)%mod;
        y/=2;
        x = (x*x)%mod;
    }
    return result;
}
bool miller(ll n, ll a) {
    if(a%n == 0) return false;
    ll k = n-1;
    while(1) {
        ll temp = power(a, k, n);
        if(temp == n-1) return true;
        if(k%2) return (temp == 1 || temp == -1);
        k /= 2;
    }
}

int isPrime(ll n) {
    if(n == 2 || n == 3) return true;
    if(n%2 == 0 || n == 1) return false;
    for(int i=0; i<5; i++) {
        ll a = a_param[i];
        if(a == n) return true;
        if(!miller(n, a)) return false;
    }
    return true;
}

int main() {
    cin>>N;
    while(N--) {
        ll S; cin>>S;
        if(isPrime(2*S+1)) ans += 1;
    }
    cout<<ans;
}