(7501) Key

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

 

 

 

밀러-라빈 소수판정법에 대해 물어보는 아파트 임대 문제를 풀고 나서 푼 문제.

입력 A와 B가 들어올 때 그 사이 홀수 K 중 (K-1)!이 K^2로 나누어 떨어지지 않는 K를 전부 구해야 한다. K가 소수라면 (K-1)!에는 K가 소인수로 없으므로 당연히 조건을 만족한다. K가 합성수라면, 원리는 잘 모르지만 르장드르의 정리를 적용하면 9를 제외한 모든 홀수 합성수에 대해 나누어 떨어진다고 한다. 9에서 예외처리만 해주고 K가 소수인지 판별하는 코드를 짜면 되며, 이때 K의 범위는 10^18까지이므로 아파트 임대에서 쓴 3개의 수보다 많은 7개의 수로 검사를 해야 100% 확률로 소수를 찾아낼 수 있다.

이때 곱셈이나 덧셈을 하는 과정에서 long 자료형의 범위에서도 오버플로우가 날 수 있기 때문에 덧셈은 모듈러 덧셈을, 곱셈은 러시아 농부 곱셈법을 이용해 분할 정복으로 구현해 __int128 등의 비표준 자료 타입 없이 long 자료형으로 계산할 수 있도록 했다.

 

 

 

#include <iostream>
using namespace std;

long millerbase[7]= {2, 325, 9375, 28178, 450775, 9780504, 1795265022};

long add(long a, long b, long mod){
  a%= mod;
  b%= mod;
  return (a>=mod-b) ? a-(mod-b) : a+b;
}

long mul(long a, long b, long mod){
  a%= mod;
  b%= mod;
  long res= 0;
  while(b){
    if(b&1)  res= add(res, a, mod);
    a= add(a, a, mod);
    b/= 2;
  }
  return res;
}

long pow(long a, long b, long mod){
  long res= 1;
  a%= mod;
  while(b){
    if(b&1)  res= mul(res, a, mod);
    a= mul(a, a, mod);
    b/=2;
  }
  return res;
}

bool miller(long x, long a){
  if(a%x==0)  return true;
  long k= x-1;

  while(1){
    long t= pow(a, k, x);

    if(t==x-1)  return true;
    if(k&1)  return (t==1 || t==x-1);

    k/= 2;
  }
}

bool isprime(long x){
  if(x==9)  return true;
  for(int i=0;i<7;i++){
    if(!miller(x, millerbase[i]))  return false;
  }
  return true;
}

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

  long a, b;

  cin >> a >> b;

  if((a&1)==0)  a++;

  for(long i=a;i<=b;i+=2){
    if(isprime(i))  cout << i << " ";
  }

  return 0;
}