• 문제를 풀어서 설명하면, n을 소인수분해했을때 지수가 가장 큰 소인수들의 곱으로 만들어질수 있는 수의 개수를 구하라는 것이다. 가장 큰 지수가 k이고, 지수가 k인 소인수가 m개라면, 답은 pow(2,m)-1 이 된다는 것을 쉽게 알수 있다.
• 결국 소인수분해만 하면 되는 문제이긴 한데, 문제에서 수가 주어지는 방식이 좀 골때린다. N을 그대로 주지 않고, N=a1*a2*..*an 으로 표현해서 ai를 입력으로 준다. 물론 이걸 진짜 다 곱해서 N을 복원한 뒤에 소인수분해를 하는 것은 N이 너무 커서 불가능하고. 대신 각각의 ai를 소인수분해한 다음에 이것들을 합쳐주는 식으로 N의 소인수분해를 구할수 있다
• 시간복잡도는 각각의 ai를 폴라드로를 이용해서 소인수분해하는데에 O(m^1/4) 이 걸리고, 이것을 n번 하니까 O(n*m^1/4)이다. 각 ai의 소인수의 개수는 O(1)개이므로, N의 소인수의 개수는 O(n)개, 즉 합치는 데에는 O(n)이면 충분하다. 지수가 가장 큰 소인수의 개수를 찾아서 답을 계산하는 것도 O(n)이면 해결된다
• 파이썬에서는 별 상관 없기는 하지만, 이렇게 구한 답의 크기는 64bit 정수 범위를 벗어날 수 있다. cpp 등에서는 큰 정수 처리를 따로 해주어야 한다
• 다 써놓고 다른사람 코드를 보다가 이것보다 더 효율적으로(10^18의 크기의 소인수분해 없이) 구하는 방법이 있다는 것을 알게 되었다. 시간날때 업데이트하겠다.

(다이아몬드 이상은 코드 비공개)

• Dependency: teflib.numtheory.prime_factorization