11397번 - 피보나미얼

피보나치 수열 \(f_n\)은 다음과 같이 정의되는 수열이다.

\[f_n = \begin{cases} 0 & \text{if }n = 0 \\ 1 & \text{if }n = 1 \\ f_{n-1} + f_{n-2} & \text{if }n \ge 2 \end{cases}\]

피보나미얼 \(F_n\) (\(n\) ≥ 1)은 \(F_n = f_1 \times f_2 \times \dots \times f_n\)으로 정의된다. 즉 \(f_1, f_2, \dots, f_n\)를 모두 곱한 값이다.

어떤 자연수 \(k\)에 대해, \(F_n\)을 \(k\)로 몇 번을 나누어야 \(F_n\)이 더 이상 \(k\)로 나누어 떨어지지 않는지를 구하는 프로그램을 작성하라.

첫 번째 줄에 두 자연수 n과 p (1 ≤ n ≤ 10⁹, 2 ≤ p ≤ 10³)이 공백을 사이로 두고 주어진다.

p - 1줄에 걸쳐 답을 출력한다. 이 중 i(1 ≤ i ≤ p - 1)번째 줄에는 F_n이 (i + 1)로 나누어 떨어지지 않도록 하기 위해 F_n을 (i + 1)로 나눠야 할 횟수를 출력해야 한다.

F₁₂ = 1,570,247,078,400 = 2⁹×3⁴×5²×...