문제 : http://oj.uz/problem/view/IOI16_molecules바로 100점 풀이.바로 100점으로 넘어가는 이유는 rkm0959의 풀이를 컨닝했기 때문. 일단 주어진 배열의 값들을 정렬한 값의 인덱스를 \(i_1, i_2, \cdots , i_n\)으로 정의한다. 이제 수학이다. \(Pro(k)\)를 다음과 같은 알고리즘으로 정의하자:\(P(k) := w_{i_1} + \cdots + w_{i_k}, \ S(k) := w_{i_n} + \cdots w_{i_{n-k+1}} \) case 1) \(P(k) > u \) : terminate (답이 없다) case 2) \(P(k) or S(k) \in [l,u] \) : terminate (둘 중 [l,u]에 들어 있는 놈이 답이다) ..

1편 : http://drugstoreoftamref.tistory.com/152편 : http://drugstoreoftamref.tistory.com/16I have no time!D20. Generalized Dirichlet Convolution$$ \text{for } x \in \mathbb{R}, \\ (a \circ F)(x) := \sum_{n \le x} a(n)F(\frac{x}{n}) $$ \(\text{cf) if } \forall x\notin \mathbb{Z} \quad F(x)=0 \ \Rightarrow \ \circ \equiv \ast \) T21. $$ a \circ (b \circ F) = (a \ast b) \circ F $$ pf) \( a \circ (b \c..

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\)의..