백준 2575 - 수열 [Python]

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

2575번: 수열

긴 수열은 3으로 쪼개고, 짧은 수열은 2 대신 4로 먼저 나누고 소인수분해 한다.

 

m = int(input())
x2 = 0
if m == 1:
    print(1, 1)
    exit()
t = m
x1 = (t + 2) // 3
 
 
while m % 4 == 0:
    m //= 4
    x2 += 1
for i in range(2, 1000001):
    while m % i == 0:
        m //= i
        x2 += 1
print(x1, x2)