MI6

• 뭘 구하라는 건지 문제를 이해하는데 가장 오래 걸렸다. 처음에는 지문을 봐도 예제를 봐도 도무지 이해가 되지 않았다..
• 하지만, 문제를 이해하고 나니까 꽤나 깔끔하고 재미있는 아이디어의 문제였다. 다만 이 아이디어를 다른 방식으로 표현할수는 없었을까..
• 여기서 요구하는 것은, 모든 그룹코드에 대해서 배정할수 있는 SIC들의 조합이 유일하게 나오도록 SIC들을 할당하라는 것이다.
• 예를 들어 생각해보자. 그룹코드가 2인 그룹이 만들어지려면, 곱해서 2가 되는 SIC의 조합이 있어야 한다. 이 조합은 {2}가 유일하므로 2번 SIC는 누군가에게 할당되어 있어야 한다. 비슷하게 그룹코드 3을 만들수 있게 하려면 SIC 3도 있어야 한다. 그러면, 그룹코드 6에 대해서 생각해보자. 2번과 3번이 있으니까 그룹코드 6은 {2,3}으로 만들수 있다. 근데, SIC가 6번인 스파이도 있다면, 그룹코드 6은 {6}으로도 만들어질수 있다. 하지만 이렇게 되면 모든 그룹이 유일한 조합을 가져야 한다는 조건에 위배되므로, 조건을 만족시키기 위해서는 SIC 6번을 갖는 스파이가 존재하지 않아야 한다.
• 이제 문제에서 요구하는 것이 어떤 것인지 감이 잡히니까.. 어떤식으로 풀어야 할지 생각해보자.
  • 그룹코드가 소수 p이면 만들 수 있는 방법은 {p} 뿐이다. 그러므로 소수 SIC는 모두 누군가에게 배정되어 있어야 한다.
  • 그룹코드가 p^2인 경우에는? 역시 서로 다른 수들의 곱으로 표현하는 방법은 없으므로 {p^2} 으로 만들어야 하고, 그러므로 p^2 에 대해서도 SIC가 존재해야 한다.
  • p^3인 경우에는? 이때는 {p, p^2} 으로 그룹이 만들어지니까, p^3 SIC가 있으면 안된다.
  • 이런식으로 일반화해보면 p^e 형태에 대해서는 e=2^k 일때만 SIC가 존재하고, 나머지는 SIC가 없어야 한다는 것을 알수 있다. 예를 들어 p=2라면, 2,4,16,256,… 에 대해서만 SIC가 존재한다. 8,32,64,128 등은 {2,4}, {2,16}, {4,16}, {2,4,16} 으로 만들어지므로 SIC가 없어야 한다. 그리고 이쯤되면 자명해지는데, 소수 인수가 2개 이상인 수에 대해서는 SIC가 없어야 한다.
• 이걸 구하는 것은 간단하다. 그룹번호를 소인수분해해서 p1^e1 * p2^e2 * … * pk^ek 형태로 만든 다음에, 다시 e1,e2,.. 를 각각 2의 거듭제곱의 합으로 분해주면 된다. e1 = 2^i + 2^j + 2^k … 이렇게 나눠진다면, p1^(2^i), p1^(2^j), p1^(2^k) 들을 답에 추가해주는 식으로 답을 구성해준다.
• 소인수분해 (Prime Factorization)는 c의 범위가 최대 10^9 이므로 폴라드로를 써서 O(n^1/4)로 구하는것이 좀더 빠르기는 하지만, O(sqrt(n)) 알고리즘으로도 충분히 돌아간다. 소인수분해 결과에서 나온 지수들을 2의 거듭제곱의 합으로 분해해주는 것은 한개당 O(log(e))이고 개수는 훨씬 더 작으므로, 전체 시간복잡도는 소인수분해의 시간복잡도에 바운드된다.

"""Solution code for "BOJ 9326. MI6".

- Problem link: https://www.acmicpc.net/problem/9326
- Solution link: http://www.teferi.net/ps/problems/boj/9326

Tags: [number theory]
"""


from teflib import numtheory


def main():
    t = int(input())
    for _ in range(t):
        c = int(input())
        factorization = numtheory.prime_factorization(c)

        answer = []
        for p, e in factorization.items():
            pow_p = p
            for c in bin(e)[:1:-1]:
                if c == '1':
                    answer.append(pow_p)
                pow_p *= pow_p

        print(*sorted(answer))


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.prime_factorization