문제.\(n\times n\) matrix \(A \ = \ (a_{ij})\)에 대해 \(s_{i} := \sum_{j=1}^{n} |a_{ij}|\)라 하자.\(A\)의 eigenvalue \(\lambda\)는 다음을 만족함을 보여라.$$ |\lambda| \le \max \left( s_{1}, s_{2}, \ldots s_{n} \right) $$ 화난다... Key observation. $$ \left\lVert v \right\rVert_{\infty} = \max \left( |v_{1}|, |v_{2}|, \ldots |v_{n}| \right) $$도 norm이다. \(\lambda\)는 eigenvalue니까, 대응되는 eigenvector를 \(v\)라고 하면\(\left\lVer..

이건 또 정수론 공부할 때 (2017.08.09) 열심히 쓰던 글이다. Inline math 가독성 극혐... 나중에 TeX으로 써서 따로 올려야겠다. 일단은 포스팅이 적혀 있는 것까지만. 추가 notation : $$ \gamma := \lim_{n \to \infty} \left( \sum_{k=1}^{n}\frac{1}{k} - \text{log} n \right) \text{ (Euler - Mascheroni const.) } $$ $$ \zeta(s) := \begin{cases} \sum_{k=1}^{\infty} \frac{1}{k^s} & {(s>1)} \\ \lim_{x \rightarrow \infty} {\left(\sum_{n \le x} \frac{1}{k^s} - \frac{x..

문제 링크 원래 1년 전 (2017.12 초)에 정수론 들을 때쯤 푼 문제인데, 포스팅 도중 계산이 틀려서 보류되었다. 얼추 기워서 올리긴 하지만 여전히 틀린 부분이 있을 수 있다. \(3k+1\) 꼴의 소수 \(p\)에 대해서 함수 \(L(m)\)을 다음과 같이 정의한다:$$ L(m) \ = \ \sum_{x = 0}^{p-1} (\frac{x(x^3 + m)}{p}) $$ 다음의 문제에 답하여라. (a) \(\forall t (\neq 0), \ m , \ L(m) = L(mt^3)\)(b) \(\mathbb{Z}_{p}^{*}\)를 다음의 조건을 만족하는 크기가 \(\frac{p-1}{3}\)인 집합 \(A,B,C\)로 분할할 수 있다:$$L(m) = \begin{cases} a & (m \in A..

AoPS 링크 A1. 다음을 만족하는 최소의 집합 \(S\)에 속하지 않는 원소로는 어떤 것이 있겠는가?- \(2 \in S\).- \(n^2 \in S \implies n \in S\).- \(n \in S \implies (n+5)^2 \in S\). 답은 \(1, 5k\).나는 그냥 bound 줄여나가면서 풀었는데, 훨씬 깔끔한 풀이가 있어서 가져왔다. \(n \in S\)에 대해서 \(n + 5 \in S\)가 자명하다. 또 2가 원소면 49가 원소고, \(54^2 = 2916\)이 \(S\)의 원소다. 이는 \(5k+1\)꼴이고, 따라서 \(2916\) 이상의 \(5k+1\) 꼴은 모두 \(S\)에 포함된다.임의의 \(5 \not{|} x\)에 대해 \(x^{16} \equiv 1 \ (\mod..

문제. \(1 \cdots n\)의 순열 \(a_{1}, a_{2}, \ldots a_{n}\)과 \(b_{1}, b_{2}, \ldots b_{n}\)에 대해, 다음 행렬 \(A\)의 행렬식으로 가능한 값을 모두 구하여라. $$ A = (A_{ij}) = ((1+a_{i}b_{j})^{n-1}) $$ \(n = 2\)일 때는 행렬을 다음의 꼴로 나타낼 수 있다. $$ A = \begin{pmatrix} 1 & a_{1} \\ 1 & a_{2} \end{pmatrix} \cdot \begin{pmatrix} 1 & 1 \\ b_{1} & b_{2} \end{pmatrix} $$ 따라서 적당한 \(k \in \{0,1\}\)에 대해 $$ \det (A) = (-1)^{k} \det \left[ \begin..

원본 Codeforces 블로그 문제를 잘 푸는 사람일수록 알고리즘을 암기하기보단 끊임없이 고찰하고, 최적화하고, 예외를 효과적으로 비껴가는 방법을 연구하는 것 같다. 그런 의미에서 이 포스팅 작성자도 굉장히 존경스럽다. 세상은 넓고 갓갓은 많아..MO's algorithm 흔히 루트질로 불리는 MO's algorithm은 배열에 대한 구간 쿼리를 오프라인으로 처리하는 많은 문제를 아슬아슬한 복잡도로 해결할 수 있게 해주는 트릭이다. kesakiyo님의 친절한 introduction 끄흐수님의 깔끔한 introduction MO's algorithm으로 문제를 풀기 위해서는 다음이 성립해야 한다 : - 구간 [s, e]에 대한 쿼리의 답을 알고 있다면, 구간 [s-1, e] 또는 [s, e+1]에 대한 ..