[BOJ 5615] 아파트 임대

https://www.acmicpc.net/problem/5615

5615번: 아파트 임대

 

- 문제 요약

 

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

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

동규부동산의 카탈로그에 적힌 아파트의 면적이 N개의( N<=100,000 / 면적 : 2^31-1 ) 줄에 순서대로 주어졌을 때, 있을 수 없는 크기의 아파트의 수를 구하는 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

문제에서 나온 아파트 방의 면적 2xy+x+y를 S라고 하겠습니다.

2xy+x+y=S라는 식에서 양변에 2를 곱하면 4xy+2x+2y=2S가 됩니다.

여기에서 양변에 1을 더하고 인수분해를 하면 (2x+1)(2y+1) =S+1라는 식을 얻을 수 있습니다.

위 식에서 우변이 소수라면 좌변이 2S+1, 1이 되므로 존재할 수 없는 면적이 됩니다.

 

그러므로 2S+1이 소수인지 판별해주면 됩니다.

입력받는 면적의 수가 최대 2^31-1이므로 밀러-라빈 소수 판별법을 사용해서 문제를 해결해 주면 됩니다.

 

https://ko.wikipedia.org/wiki/%EB%B0%80%EB%9F%AC-%EB%9D%BC%EB%B9%88_%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95

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

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long int ll;
ll arr[]={2,7,61};

ll f(ll x,ll y,ll mod){
	ll res=1;
	x%=mod;
	while(y){
		if(y%2){
			res=(res*x)%mod;
		}
		y/=2;
		x=(x*x)%mod;
	}
	return res;
}

bool miller(ll n, ll a){
    if(a%n==0){
    	return true;
	}
    ll k=n-1;
    while(true){
        ll tmp=f(a,k,n);
        if(tmp==n-1){
        	return true;
		}
        if(k%2){
        	return (tmp==1||tmp==n-1);
		}
        k/=2;
    }
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,result=0;
	cin>>n;
	ll a;
	for(int i=1;i<=n;i++){
		cin>>a;
        a=a*2+1;
        for(int j=1;j<=3;j++){
            if(miller(a,arr[j-1])==false){
                result++;
                break;
            }
        }
	}
	cout<<n-result;
}

코드 제출 결과