백준 7501번: Key (C++)

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

7501번: Key

---

Solved By: Miller-Rabin

 

주어진 a, b 사이에 존재하는 홀수 K에 대해 다음을 묻습니다.

K^2으로 (K - 1)!을 나눌 수 없다는 조건을 만족하는 홀수 K를 구하라.

 

'K^2으로 (K - 1)!을 나눌 수 없다'는 말은 (K - 1)!은 K^2를 약수로 가지지 않는다는 말과 같습니다.

즉, (K - 1) * (K - 2) * (K - 3) * ... * 2 * 1 중에 K가 최대 한 번만 나온다는 뜻입니다.

 

만약 K가 소수라면 어떤가요.

소수 K는 자기 자신과 1만을 약수로 가지기 때문에 (K - 1) ~ 1까지 중에는 K가 단 한 번도 나올 수가 없습니다.

즉, K가 소수라면 K를 출력하면 됩니다. 소수 판정할 수가 꽤 많기 때문에 Miller-Rabin을 사용했습니다.

 

하지만, 여기서 끝이 아닙니다. 예외가 하나 있습니다.

K가 9 = 3^2라면 (K - 1)!에서 (K - 1) ~ 1까지의 모든 인수 중 3이 최소 4번 이상 나왔어야 하지만 6과 3에서 밖에 나오지 않습니다.

 

그렇다고 해서 다른 홀수의 제곱수를 체크해봤지만 모두 K^2은 (K - 1)!의 인수가 되기 때문에 9만 예외 처리를 해주면 됩니다.

#include <iostream>
#define ull unsigned long long
using namespace std;

ull power(__int128 a, __int128 b, __int128 mod){
    __int128 ret = 1;
    while(b > 0){
        if(b % 2) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return (ull)ret;
}

bool millerRabin(ull n, ull a){
    if(a % n == 0) return true;
    ull k = n - 1;
    while(true){
        ull temp = power(a, k, n);
        if(temp == n - 1) return true;
        if(k % 2) return (temp == 1 || temp == n - 1);
        k /= 2;
    }
}

bool isPrime(ull n){
    if(n == 2) return true;
    else if(n % 2 == 0) return false;
    else{
        ull base[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        for(auto a : base){
            if(n == a) return true;
            if(!millerRabin(n, a)) return false;
        }
        return true;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    ull a, b; cin >> a >> b;
    if(a % 2 == 0) a++;
    
    for(ull i = a; i <= b; i += 2){
        if(isPrime(i)) cout << i << ' ';
        else if(i == 9) cout << 9 << ' ';
    }
}