$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$
Codeforces Round #618 (Div. 1) 후기 + 풀이
Predictor에 +116이라고 뜨는 것과는 달리, 실제로는 +115를 받아서 2099점이 되었다. 오렌지 갔나 했는데, :blobsad: ㅠㅠ 라운드는 굉장히 재밌게 했던것 같다. A. Anu has a function 수열 $a_1, a_2, a_3 \dots a_n$ 과 함수 $f(x, y) = (x | y) - y$ 이 주어질 때, 이들을 적당히 재배열해서 $$f(f(\dots f(f(a_1, a_2), a_3), \dots a_{n-1}), a_n)$$ 의 값을 최대화하는 문제. 잘 생각해 보면, $f(x, y)$ 는 $x$의 On bit 들을 모은 집합에서 $y$의 On bit 들을 모은 집합의 차집합을 반환한다는 사실을 알 수 있다. 즉, 최대한 '가치' 가 높은 비트(큰 비트) 들을 살리..
해석개론 - 연습문제 1.6.7
[출처] : 김김계 해석개론 연습문제 1.6.7 문제 임의의 자연수 $n = 1, 2, \dots$ 에 대하여, $\sqrt{n-1} + \sqrt{n+1}$ 은 무리수임을 보여라. 먼저, 주어진 수 $x = \sqrt{n-1} + \sqrt{n+1}$ 에 대해, $x^2 = 2n + 2 \sqrt{n^2-1}$ 이다. 따라서, $\sqrt{n^2-1}$이 모든 자연수에 대하여 무리수임을 보이는 것으로 충분하다. (만약 $x$가 유리수라면 $x^2$ 도 유리수이고, 이때 $\sqrt{n^2-1}$ 이 무리수일 수 없으므로) 어떤 수 제곱수 $a^2$ 과 $b^2$ 에 대해 $a^2+1 = b^2$ 이면, $(b-a)(b+a) = 1$ 이어야 하고 $b>a, a, b \in \N$ 이어야 하는데 이러한 두..