이 문제에서 구하려는 함수는 다음과 같다. 함수 $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..

굉장히 어려운 문제이다... 코드업에 비슷한 문제를 냈었는데 그거보다 어렵다 ㅜㅜ 하지만 무려 8일간 고민을 거듭해서 맞았다! 그 풀이에 대해 적어보려고 한다! 문제 등차수열에 관한 디리클레의 정리는 서로소인 두 양의 정수 a와 b가 있을 때, 등차수열 t(n) = a*n + b (n ≥ 0)은 무한히 많은 소수를 포함한다는 내용이다. 소수는 2보다 큰 양의 정수로, 약수가 1과 자기자신 밖에 없는 수이다. 예를 들어, a=4, b=3인 경우 등차수열은 다음과 같다. 3, 7, 11, 15, 19, 23, 27, 31, 35, ..., 여기서 이 등차수열의 첫 부분에 많은 소수가 있음을 눈으로 볼 수 있다. a > 0과 b ≥ 0, 그리고 U ≥ L ≥ 0이 주어졌을 때, t(n) = a*n+b에 소수가..