Definition.\(\phi(n)\) : Number of natural numbers in \(1..n\), which are relatively prime to \(n\).\(\sigma(n)\) : Sum of divisors of \(n\), including \(1\) and \(n\) itself.claim.$$n > 1 \Rightarrow \phi(n) > \frac{n}{4\log n}$$This section is intentionally left blank. Special thanks: H. Cho, W. Song. Solution 1. (Official) \(n := p_{1}^{e_1} p_{2}^{e_2} \cdots p_{k}^{e_k}\). $$ \phi(n) = n \p..

트리 / 그래프의 기본기인 DFS technique를 연습하려고 한다.너무 쉬운 건 말고, Div.1 A ~ B 부터 짬짬이 풀어야지. 링크 396C. On Changing Tree 코드 트리에 기본적으로 DFS numbering을 해주자.잘 모르겠다면 코드, 또는 다음 설명을 참조. 노드 \(v\)가 발견되는 시점을 \(dt[v]\), 노드 \(v\)의 탐색이 끝나는 시점을 \(ft[v]\), 노드 \(v\)의 깊이를 \(dep[v]\)라고 한다.합 세그먼트 트리를 2개 관리한다. 각각 \(X, K\)라고 하자. type 1 쿼리 \((v,x,k)\) :\(X\)의 \([dt[v], ft[v]]\)에 \(x + k \cdot dep[v]\)를 더해줌.\(K\)의 \([dt[v], ft[v]]\)에 \(..

말그대로 여기서 태그에 DnC가 붙어 있는 놈들을 풀어보려는 시도입니다. 백준에서 좋은 DnC 찾기가 너무 힘들어서... 559B. Equivalent Strings 559B 문제가 말하는 "동치 관계"가 정말로 equivalent relation의 조건을 만족시킨다는 것이 관찰 포인트이다.그렇다면 한 string \(S\)의 대표원 \(r_{S}\)를 정해줄 수 있고, 편의상 사전 순으로 가장 빠른 string으로 정해주면 된다. 어떤 길이가 짝수인 string \(S = A + B\)에 대해서 \(r_{S} = \text{min}(r_{A} + r_{B}, r_{B} + r_{A})\)로 정해질 것이므로, 시간복잡도는 \(T(n) = 2T(\frac{n}{2}) + \) (문자열 비교하는 시간) \(..

Gamma Function은 여러 가지 정의가 있는데, 그 중 몇 가지 정의들은 서로 동치임이 자명하지만은 않다.여기서는 가장 대표적인 동시에 가장 대립되는 두 가지 정의를 다룬다.

여름방학 때부터 3단원을 정리하려고 했지만 너무 귀찮아서 패스.4단원은 \(\pi (x)\)를 신나게 갖고 노는 1부와, 소수 역수의 합을 가지고 노는 2부로 나뉘어서 업로드됩니다.

스포방지를 위해서 먼저 문제만 올린다. 1. 다음을 만족하는 함수 \(f : \mathbb{N} \to \mathbb{N}\)를 모두 찾으시오 : $$ \forall m, n \ n + f(m) | f(n) + nf(m) $$ 2. 다음을 만족하는 함수 \(f : \mathbb{R} \to \mathbb{R}\)를 모두 찾으시오 :$$ \forall x, y \ f(x^4 + f(y)) = f(x)^4 + y $$ 솔루션은 LaTeX로 작성해봤는데, section 커스터마이징하다가 문서 다 깨지고 멘탈도 blow - up 당해서 결국 다 날리고 새로 타이핑했다. 가독성 따위 개나 줘버려랏! 히히힛!