피보나치 수열 $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$이 주어졌을 때, 다음 두 조건을 만족하는 양의 정수 $x$의 개수를 구해보자. - $x$는 $n$의 배수이다 - $x$의 양의 약수의 개수는 $n$개이다. $x$가 $n$의 배수이니 적어도 $x$는 $n$의 소인수들을 모두 갖고 있습니다. $n=p^{c}$($p$는 임의의 소수, $c$는 임의의 자연수)라고 해봅시다. 만약 임의의 소수 $q$에 대해 $x=p^{p^{c-1}-1}q^{p-1}$이라면 $q$를 마음껏 정할 수 있기 때문에 경우가 무한개가 될 것입니다. 이를 만족하기 위해서는 $p^{c-1}-1 \ge c$이면 됩니다. 가장 작은 소수인 2에 대해서 생각해봅시다. $2^{c-1} \ge c+1$을 만족해야 합니다. 이 부등식은 $c=3$일 때부터 성..

우리가 이용할 식은 아래와 같습니다. $\gcd(f_{n},f_{m})=f_{\gcd(n,m)}$ 위 성질을 증명해봅시다. $\gcd(f_{k+1},f_{k})$ $\gcd(f_{k+1},f_{k})=\gcd(f_{k},f_{k-1})=\gcd(f_{k-1},f_{k-2})=...=\gcd(f_{2},f_{1})=1$ $f_{k} | f_{nk}$ $n=1$일 때 $f_{k} | f_{k}$임은 자명합니다. $n=a$일 떄 $f_{k} | f_{ak}$라고 가정합시다. $f_{(a+1)k}=f_{ak}f_{k-1}+f_{ak+1}f_{k}$ 그럼 이때! 가정에 의해 $f_{k} | f_{(a+1)k}$가 성립합니다! 따라서 수학적 귀납법에 의해 $f_{k} | f_{nk}$라고 말할 수 있죠! $\gcd..

피보나치 수열 $F$와 황금비 $\phi$, 음이 아닌 자연수 $n,k$에 대해 어떤 정수 $A,B$가 아래 식을 만족할 때 $A,B$를 구하는 것이 우리의 목표에요! $(F_{n}\phi+F_{n-1})^{k}=A\phi^{k}+B$ 우린 한가지 성질을 알고 가야 하죠! $\phi^{n}=F_{n}\phi+F_{n-1}$ 이를 증명해봅시다. $\phi^{n}=F_{n}\phi+F_{n-1}$ $n=1$일 때 $\phi=F_{1}\phi=\phi$ 로 성립하네요. $n=2$일 때 $\phi^{2}=F_{2}\phi+F_{1}=\phi+1$ $\cdot\cdot\cdot *$ $\phi$는 방정식 $x^{2}=x+1$의 한 근이므로 위 식 역시 성립해요. $n=k$일 때 $\phi^{k}=F_{k}\phi..

문제 제목부터 공감이 간다. 아무튼 문제를 풀어보자. 어떤 양의 정수 $n$이 있다고 할 때, $x\phi(x) = n$을 만족하는 양의 정수 $x$가 존재하는가? 이때 $\phi(x)$는 오일러 피 함수이다. 사실 이 문제는 매우 간단하다! $x$가 $n$을 나누기 때문에 $n$의 약수를 찾으면 된다. 또 $\phi(x)$를 계산해야하는데 이는 $x$를 인수분해 하면 되고 $O(\sqrt{x})$이 걸린다. $n$의 약수를 인수분해 하므로 $n$의 가장 큰 약수가 시간복잡도에 지배적이라고 보면 $O(\sqrt{n})$이라고 볼 수 있다. 약수를 찾는과정은 $O(\sqrt{n})$의 시간이 걸린다. 따라서 전체 시간 복잡도는 $O(2\sqrt{n})$이다. 오일러 피 함수 설계 방식을 설명하겠다. 이해가..

이 문제에서 구하려는 함수는 다음과 같다. 함수 $S$는 다음과 같이 정의된다. $S(0,\ n) = n$ (모든 양의 정수 $n$) $S(k,\ n) = S(k-1,\ 1) + S(k-1,\ 2) + ... + S(k-1,\ n)$ (모든 양의 정수 $k,\ n$) 이때 $S(k, n)$을 적절히 변형시켜보자. $S(k,\ n) = S(k-2,\ 1) + [S(k-2,\ 1) + S(k-2,\ 2)] + [S(k-2,\ 1)+S(k-2,\ 2)+S(k-2,\ 3)] + ...$ $= nS(k-2,\ 1) + (n-1)S(k-2,\ 2) + (n-2)S(k-2,\ 3) + ... $ 정의에 의해서 $= nS(k-3,\ 1) + (n-1)[S(k-3,\ 1)+S(k-3,\ 2)] + (n-2)[S(k-3,..