(5615) 아파트 임대

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

단계별로 풀어보기

56단계(수학 3) 2번째

 

 

 

면적이 s라고 하면 2s+1은 4xy+2x+2y+1=(2x+1)(2y+1)이다. x와 y가 양의 정수라고 했으므로 이 수는 합성수이다. 만약 2s+1이 소수라면 s 크기의 아파트는 있을 수 없다. 소수 판정을 일반적인 O(√N)으로 하면 시간 초과가 나므로 O(log N)의 밀러-라빈 소수판정법을 써야 한다. 밀러-라빈 소수판정법은 페르마의 소정리를 변형해 소수 여부를 '확률적'으로 판별하는 방법이다.

결론만 말하자면 N이 소수라면 N-1=d*2^s(d는 홀수)일 때, 임의의 base값 a에 대해 모듈러 N 공간에서 a^d ≡ 1이거나 a^(d*2^r) ≡ -1인 0이상 s미만의 정수 r이 존재해야 한다. 위에서 말했듯이 이 방식은 확률적이기 때문에 무작위로 여러 a에 대해 판별해야 하지만, 판별하는 수 N이 일정 값 이하일 땐 100%로 소수를 판정하는 밑의 집합이 알려져 있다. 이 문제에서 N은 2^32 미만이므로, a= 2, 7, 61 세 개에 대해 검사해 전부 참이 나오면 N은 소수라고 할 수 있다.

 

 

 

#include <iostream>
using namespace std;
typedef unsigned long ul;

ul power(ul base, ul expo, ul p){
  ul res= 1;
  base%= p;
  
  while(expo){
    if(expo&1)  res= (res*base)%p;
    base= (base*base)%p;
    expo/= 2;
  }
  
  return res;
}

bool miller(ul x, ul a){
  if(a%x==0)  return true;
  
  ul k= x-1;
  while(!(k&1))  k/= 2;
  
  ul t= power(a, k, x);
  if(t==1||t==x-1)  return true;

  while(k<x-1){
    t= (t*t)%x;
    
    if(t==x-1)  return true;

    k*= 2;
  }
  
  return false;
}

bool isprime(ul x){
  if(!miller(x, 2))  return false;
  if(!miller(x, 7))  return false;
  if(!miller(x, 61))  return false;

  return true;
}

int main() {
  int n, ans= 0;
  
  cin >> n;
  
  while(n--){
    ul s;

    cin >> s;

    if(isprime(s*2+1))  ans++;
  }
  
  cout << ans;

  return 0;
}