[BOJ 11397] 피보나미얼

피보나치 수열 $f_n$에 대해

$F_{n}=f_{1}f_{2}f_{3} \cdot\cdot\cdot f_{n}$

으로 정의되는 수열 $F_{n}$이 어떤 수로 몇 번 나누어 떨어지는지 계산하는 문제이다.

 

이 문제의 핵심은 $\gcd(f_{n},f_{m})=f_{\gcd(n,m)}$임을 이용하는 것이다.

주어진 수가 $n$이라 하고 직접 계산해보자. 또, $F_{n}$이 2로 나누어 떨어지는 횟수를 $g_2$라고 하자.

$f_3$은 2이다. 그럼 $f_{3m}$은 전부 2의 배수가 됨을 알 수 있다. 

$g_{2}$+=$\lfloor \frac{n}{3} \rfloor$

$f_6$은 8이고 6은 3의 배수로 이미 한번 센 수를 빼면 2는 2개가 된다.

$g_{2}$+=$2\cdot \lfloor \frac{n}{6} \rfloor$

이렇게 계속 $f_{3\cdot 2^{m}}$ 꼴 수에 대해 계산하면 2로 나누어 떨어지는 횟수를 얻는다. 9 이상의 수는 모두 2의 거듭제곱이 1개씩 늘어난다.(아직 증명하지 못했다.)

 

$f_{m}$이 소수 $p$로 나누어떨어지는 최소의 $m$을 모두 저장해두고 그 수들부터 $ans$값을 계산한다.

$F_{n}$을 합성수($m$)로 나누어 떨어지는 횟수를 계산해보자. $m=p_{1}^{e_{1}}p_{2}^{e_{2}}...p_{k}^{e_{k}}$라고 하자.

$g_{p}$를 $F_{n}$이 $p$로 나누어 떨어지는 횟수라고 하자. 이때

$g_{m}=min(\lfloor \frac{g_{p_{1}}}{e_{1}} \rfloor, \lfloor \frac{g_{p_{2}}}{e_{2}} \rfloor,...,\lfloor \frac{g_{p_{k}}}{e_{k}} \rfloor)$

 

이 과정은 아래 코드로 구현해 놓았다.

 

코드 보기

def sol(n,st,p):
    ans=0
    if p==2:
        ans+=n//st
        st*=p
        while n//st:
            if st==6:
                ans+=n//st*2
            else:
                ans+=n//st
            st*=p
    else:
        while n//st:
            ans+=n//st
            st*=p
    return ans
 
def fac(n):
    ans=[0]*1010
    while n%2==0:
        n//=2
        ans[2]+=1
    for i in range(3,int(n**0.5)+1,2):
        while n%i==0:
            n//=i
            ans[i]+=1
        if n==1:
            break
    if not n==1:
        ans[n]+=1
    return ans
            
n,p=map(int,input().split())
num=[0] * 1010
prime=[2]
st=[]
 
for i in range(3,int(1000**0.5)+1,2):
    if num[i] or i%2==0:
        continue
    for j in range(i*i,1000,i):
        num[j]=1
 
for i in range(3,1000,2):
    if num[i]==0:
        prime.append(i)
 
for i in prime:
    a,b,cnt=0,1,0
    while 1:
        s=a+b
        a=b
        b=s
        cnt+=1
        if s%i==0:
            break
    st.append(cnt+1)
 
for i in range(2,p+1):
    ans=1e9
    c=fac(i)   
    for j in range(2,i+1):
        if c[j]==0:
            continue
        ind=prime.index(j)
        ans=min(ans,sol(n,st[ind],j)//c[j])
    print(ans)