1편 : http://drugstoreoftamref.tistory.com/15Qkffl Qkffl dmdkdkdkdkdkdD12. (Completely) Multiplicative Function MF : \(f \text{ s.t. } f(mn)=f(m)f(n) \ \forall m,n \text{ s.t. }gcd(m,n)=1\) CMF : \(f \text{ s.t. } f(mn)=f(m)f(n) \ \forall m,n \) * 앞으로 MF들의 집합을 \(\mathbb{M}\)으로, CMF들의 집합을 \(\mathbb{CM}\)으로 denote. C12-1. $$f \in \mathbb{M} \Rightarrow f(1)=1$$ T13. $$f \in \mathbb{M} \Leftrightarr..

Apostol의 해석적 정수론을 공부해 보았다. 대부분 증명을 혼자 쓰다 보니 오류가 있을 수도...? 오류 제보 환영합니다.Notation :D : DefinitionT : Thm.C : Corollary별 말 없으면 \(p\)는 소수D1. (Mobius Func.) \( \mu(n) = \begin{cases} 1 \quad (n = 1) \\ 0 \quad (\exists \ p \ s.t. \ p^{2} | n) \\ {(-1)}^{\omega(n)} \quad (otherwise) \end{cases}\)( \(\omega(n)\) : \(n\)의 서로 다른 소인수 개수) T2. $$ \sum_{d|n}{\mu(d)} = I(n) = \lfloor \frac{1}{n} \rfloor $$ pf)..

그 동안 쉬운 문제만 푸느라 문제 정리를 올리고 싶은 의욕이 없었다. 앞으로는 그냥 의식의 흐름대로 풀리는 문제는 적당히 필터링하겠다. 1052. 물병http://icpc.me/1052 일단 물병을 무한정으로 사올 수 있기 때문에, 항상 답을 찾을 수 있다. 그냥 입력의 \(N\)보다 큰 최소의 \(2^p\)꼴의 숫자를 찾으면 물병을 1개로 만들 수 있기 때문에, 답은 항상 \(2N\)보다 작다는 것도 알 수 있다.그런데 그대로 내면 당연히 4%대에서 틀리게 된다. 아이디어를 조금만 발전시키자. \(X\)개의 물병을 압축할 수 있는 최소 개수는 \(X\)를 이진수로 나타냈을 때 각 자리수의 합, 즉 \(s_2 (X)\)가 됨을 알 수 있다. 즉 물병을 더해 가면서 \(s_2 (X) \le K\)가 성립하..

5485. 평균값 수열 (IOI '05) http://icpc.me/5485 이 문제에서 가장 중요한 아이디어는 \(s_1\)과 \(m_1 \cdots m_{n-1}\)만으로 \(s_2 \cdots s_n\)을 결정할 수 있다는 것이고, 따라서 가능한 수열의 개수는 가능한 \(s_1\)의 개수와 같다는 것이다.수열의 단조 증가 조건으로부터,\(s_2 = 2m_1 - s_1 \ge s_1 \Rightarrow s_1 \le m_1\)\(s_3 = 2m_2 - s_2 \ge s_2 \Rightarrow s_1 \ge 2m_1 - m_2\)\(s_1 \le 2m_1 - 2m_2 + m_3\)\(\vdots\)와 같이 \(s_1\)에 관한 총 \(n-1\)개의 부등식을 얻을 수 있고, 이를 통해 \(s_1\)의..

2820. 자동차 공장 문제 : http://icpc.me/2820 세그먼트 트리의 클래식한 활용 문제. 사실 suhgyuho가 준 문제집에 있던 건데 이제서야 풀었다(...) 이 문제의 아이디어는 트리를 Segment Tree나 Fenwick Tree같은 구간 자료구조와 엮을 때 자주 쓰는 트릭 중 하나인데, 어떤 노드 \(v\)의 서브트리 (\(v\) 포함) 를 DFS-numbering에서 붙은 번호 \([d[v], f[v]]\)의 구간으로 처리하는 것이다. 이 트릭을 적용하고 나면 문제의 쿼리는 이렇게 바뀐다 : p 쿼리 : 구간 \((d[a],f[a])\)의 원소에 \(x\)를 더한다. (range update)u 쿼리 : 구간의 \(d[a]\)번째 원소의 값을 구한다. (point query) ..

3584. 가장 가까운 공통 조상 문제 : http://icpc.me/3584 옛날 ICPC문제여서 그런지 진짜 LCA를 대놓고 묻는 문제. 이 때는 아직 LCA가 고ㅡ급 알고리즘이었나보다. 테스트 케이스마다 배열 초기화에 주의하도록 하자. LCA에 대해서는 더 잘 설명해놓은 글들이 천지빽가리.http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220820773477 Time Complexity : \(O(Tn)\) 8984. 막대기 (KOI '13)문제 : http://icpc.me/8984http://oj.uz/problem/view/KOI13_game BOJ AC 기준으로 게시.문제 조건을 잘못 이해해서 이거 완전 NP 아니냐? 하고 풀이를 깠다. 이해..