전체 글(77)
-
[BOJ 19577] 수학은 재밌어
문제 제목부터 공감이 간다. 아무튼 문제를 풀어보자. 어떤 양의 정수 $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})$이다. 오일러 피 함수 설계 방식을 설명하겠다. 이해가..
2021.08.16 -
[BOJ 13430] 합 구하기
이 문제에서 구하려는 함수는 다음과 같다. 함수 $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,..
2021.08.15 -
[Codeup 2534] 무리수 거듭제곱
무리수를 직접 거듭제곱 하기에는 부동소수점 오차가 존재하기 때문에 부적절하다. 우리는 새로운 방법을 찾아야 한다. 문제에서 주어진 무리수가 $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..
2021.08.15 -
반사
$\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..
2021.07.28 -
페르마의 두 제곱수 정리
$p=4m+1$형태를 갖는 모든 소수는 제곱수 두 개의 합으로 표현된다. 즉, $p=x^{2}+y^{2}$으로 쓸 수 있는 적당한 양의 정수 $x,y \in \mathbb{N}$가 존재한다. 몇 가지 명제를 증명한 후에 본격적인 증명을 해보자. 두 제곱수의 합으로 표현되는 두 수를 곱하면 그 역시 두 제곱수의 합으로 표현할 수 있다. $(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$ 어떤 두 제곱수의 합인 수 $a^2+b^2$가 두 제곱수의 합인 소인수 $c^2+d^2$를 갖는다면, 몫 $(a^2+b^2)/(c^2+d^2)$은 두 제 곱수의 합이다 위 가정에 의해 다음이 성립한다. $c^2+d^2 | c^2(a^2+b^2)-a^2(c^2+d^2)=(bc+ad)(bc-ad)$ 이때 ..
2021.07.27 -
[BOJ 4798] 등차수열에 관한 디리클레의 정리
굉장히 어려운 문제이다... 코드업에 비슷한 문제를 냈었는데 그거보다 어렵다 ㅜㅜ 하지만 무려 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에 소수가..
2021.06.02