문제
창영이는 심심해서 혼자 재미 없는 게임을 하나 생각해냈다. 숫자 N을 먼저 정하고, 이 숫자를 2진법, 3진법, 4진법, ..., 100만진법, 100만 1진법 등등으로 바꾸어 보면서, 마지막자리에 연속된 0의 개수를 모두 더하는 것이다.
예를 들어 N=5라면, 2진법 101, 3진법 12, 4진법 11, 5진법 10, 6진법 5, 7진법 5, ... 등과 같으므로 답은 1이 된다. 여러분이 할 일은 주어진 N에 대해서 창영이가 구한 답을 찾는 것이다. 정확히 설명하기 위해 수학식으로 쓰자면, f(N, b)를 N을 b진법으로 나타냈을 때 마지막에 따르는 연속된 0의 개수로 정의 할 때
를 구하는 것이다.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다. 다음 T줄에 걸쳐서 N이 주어진다.
출력
각 줄에 위 수식에 대한 답을 출력한다.
제한
1 ≤ T ≤ 100,000
1 ≤ N ≤ 1,000
풀이
계속 시간초과가 떠서 PyPy3 로 해봤더니 통과됐다.. ㅎ.......머쓱
from sys import stdin
case = int(stdin.readline())
for i in range(case):
num = int(stdin.readline())
res = 0
for j in range(2, 1001):
N = num
while True:
if N % j == 0:
res += 1
N //= j
else:
break
print(res)2진수로 생각해봤을때 N = 5 일때
2 | 5
2 | 2 ...1
| 1 ...0이므로 왼쪽부터 아래에서 위로 101 이 된다. 따라서 처음 %2 를 했을때 0 이 되면 그것이 맨 뒤에 위치한 0이 되므로 계속 %2 하여 0이 안되는 순간 break 하면 된다.
