[BOJ] 9326 - MI6

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

BOJ - MI6

문제 유형: 수학, 정수론, 소수판정

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 128MB

 

문제

MI6는 스파이의 신원을 확인하기 위해서 스파이 식별 코드(Spy Identification Code, SIC)를 사용한다. 예를 들어, 제임스 본드의 SIC는 7이다.

MI6는 스파이의 그룹과 그룹에 속하는 스파이를 쉽게 알아볼 수 있게 하기 위해 SIC를 할당한다. 그룹은 상태 코드로 나타낼 수 있는데, 상태 코드는 그룹에 속하는 모든 스파이의 SIC를 곱한 값이다.

상태코드의 효율성을 위해, 2보다 크거나 같은 모든 상태코드에 대해서, 각 상태코드를 가지는 스파이 그룹이 유일하게 존재하고, 각 스파이 그룹사이의 상태코드 값이 다르게 되도록 SIC를 배정하려 한다.

상태 코드가 주어졌을 때, 그 그룹에 속하는 스파이의 SIC를 모두 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다. 각 테스트 케이스의 첫째 줄에는 상태 코드 c (2 ≤ c ≤ 10^9)가 주어진다.

 

출력

각 테스트 케이스 마다, 입력으로 주어진 상태 코드에 속하는 스파이의 SIC를 오름차순으로 출력한다. SIC 사이에는 공백을 하나 출력한다.

 

풀이

유일하게 스파이 그룹을 구성하려면, 다음과 같이 구성하여야 한다:

인수분해 시, 소수의 2의 승수번째 제곱들의 곱으로만 이루어져야 한다.

즉, 소인수들의 1, 2, 4, 8, ...승들의 곱으로만 이루어져야 한다.

예제가 큰 힌트가 되어준다.

 

소인수 2부터 시작해서, 소인수의 제곱이 c보다 작은동안, 다음을 반복한다:

 1. c % i로 나누어떨어지는 동안, c에 i를 나누면서 i가 몇 번 곱해지는지 카운트해준다.

 2. 약수로 i ^ cnt를 가지는 것을 알았으니, cnt를 이진 표현 했을 때, 1인 자릿수들에 대해 스파이의 구성 요소로 넣어준다.
예를 들면, 2를 6개 가진다면, 2^2 * 2^4를 가진다는 뜻이다.

만약 루프가 끝나고 c가 1보다 크다면, sqrt(c)보다 큰 약수가 하나 남았다는 뜻인데, 남는 경우, 이는 큰 수의 스파이 구성원이 됨을 알 수 있다. 작은 소인수들로 최대한 나눈 나머지이기 때문이다.

 

이렇게 구성원들을 모은 배열을 오름차순 정렬하고, 출력해주면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll bpow(ll base, ll exp) {
    ll res = 1;
    while (exp) {
        if (exp & 1) {
            res = res * base;
        }
        exp >>= 1;
        base = base * base;
    }

    return res;
}

void solve() {
    ll c;
    cin >> c;

    vector<int> ans;

    ll i = 2;
    while (c > 0 && i * i <= c) {
        ll cnt = 0;
        while (c % i == 0) {
            cnt++;
            c /= i;
        }
        if (cnt == 0) {
            i++;
            continue;
        }
        int shift = 0;
        while (cnt) {
            if (cnt & 1) {
                ans.emplace_back(bpow(i, 1 << shift));
            }
            cnt >>= 1;
            shift++;
        }
        i++;
    }
    if (c > 1) {
        ans.emplace_back(c);
    }
    sort(ans.begin(), ans.end());

    for (const auto &elem : ans) {
        cout << elem << " ";
    }
    cout << "\n";
}

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}