[Baekjoon - 9176] 메르센 합성수

난이도: Gold IV

 

태그

• Precomputation
• Primality Test

 

풀이

1. \( K \)의 범위가 많이 작은데...

가능한 모든 소수 \( p \)에 대해 \( 2^p - 1 \)의 소인수분해 결과를 미리 저장해둡시다.

 

이는 제출 코드가 아닌 다른 코드를 사용해서 전처리를 해주는 방식으로 처리할 수 있습니다.

 

2. 주의사항

\( 2^{61} - 1 \)은 소수입니다.

 

만약 \( O(\sqrt{N}) \) 시간의 소수 판정/소인수분해를 하고 있다면, \( K = 61 \)에서 continue를 하는 걸 추천합니다.

사실 \( K = 61 \)만 제외하면 그냥 제출 코드에서 돌려도 될 정도로 빠르게 돌아갑니다.

 

3. 코드(로 추정)

string res[70];
 
void Main(){
    res[11] = "23 * 89 = 2047 = ( 2 ^ 11 ) - 1";
    res[23] = "47 * 178481 = 8388607 = ( 2 ^ 23 ) - 1";
    res[29] = "233 * 1103 * 2089 = 536870911 = ( 2 ^ 29 ) - 1";
    res[37] = "223 * 616318177 = 137438953471 = ( 2 ^ 37 ) - 1";
    res[41] = "13367 * 164511353 = 2199023255551 = ( 2 ^ 41 ) - 1";
    res[43] = "431 * 9719 * 2099863 = 8796093022207 = ( 2 ^ 43 ) - 1";
    res[47] = "2351 * 4513 * 13264529 = 140737488355327 = ( 2 ^ 47 ) - 1";
    res[53] = "6361 * 69431 * 20394401 = 9007199254740991 = ( 2 ^ 53 ) - 1";
    res[59] = "179951 * 3203431780337 = 576460752303423487 = ( 2 ^ 59 ) - 1";
    int k; cin >> k;
    for (int i = 1; i <= k; i++){
        if (res[i].size()){ cout << res[i] << endl; }
    }
}