우리가 이용할 식은 아래와 같습니다. $\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,..

무리수를 직접 거듭제곱 하기에는 부동소수점 오차가 존재하기 때문에 부적절하다. 우리는 새로운 방법을 찾아야 한다. 문제에서 주어진 무리수가 $a+b\sqrt{c}$라고 하자. 또 이 무리수의 켤래 무리수를 $a-b\sqrt{c}$라고 잡을 수 있다. 두 무리수는 다음 방정식을 만족하는 두 근이다. $x^{2}-2ax+a^{2}-b^{2}c=0$ 또 양변에 $x$를 많이 곱하면 $x^{n}-2ax^{n-1}+(a^{2}-b^{2}c)x^{n-2}=0$ 이 된다. 각각의 근을 $\alpha, \beta$라고 하면 $\alpha^{n}-2a\alpha^{n-1}+(a^{2}-b^{2}c)\alpha^{n-2}=0$ (1) $\beta^{n}-2a\beta^{n-1}+(a^{2}-b^{2}c)\beta^{n-2..

$\overline{AB}$와 $\overline{BC}$가 이루는 각을 $\phi$라고 합시다. $A$에서 레이저를 쏴서 $\overline{BC}$, $\overline{AB}$에 순서대로 반사된 점들을 각각 $A_{n}$ ($n=2,3,4$)라고 합시다. 또 각각의 길이를 $L_{n}$ ($n=1,2,3...$)라고 하고 해당 선분이 $\overline{AB}$와 이루는 각을 $\theta_{n}$ ($n=1,2,3...$)이라고 합시다. 예를 들면 $\overline{AA_{2}}=L_{1}$이 되는거죠! 각의 변화 알아보기 $\angle CA_{2}A$를 찾아봅시다. $A_{2}$에서 $\overline{AB}$와 평행한 직선을 긋고 동위각에 의해 $\angle CA_{2}D = \angle C..