PS/백준(42)
-
[BOJ 1770] 배수와 약수의 개수
문제는 다음과 같습니다. 양의 정수 $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$일 때부터 성..
2021.08.21 -
[BOJ 11778] 피보나치 수와 최대공약수
우리가 이용할 식은 아래와 같습니다. $\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..
2021.08.21 -
[BOJ 10908] Phibonacci
피보나치 수열 $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..
2021.08.21 -
[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 -
[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