* 본 포스팅은 학교 내 양자컴퓨터 수업을 정리하기 위한 포스팅으로 다른 포스팅에 비해 길이가 짧고, 내용상의 하자가 있을 수 있습니다. Vector Space 양자역학의 언어는 기본적으로 선형대수학이다. 개중 양자컴퓨터에 필요한 선형대수학은 이 정도로 정리할 수 있다. KetVector Space \(V\)의 원소를 켓(ket)이라고 하며, \(\left|\psi\right>\)와 같이 표기한다. 양자역학에서는 어떤 계의 '상태' 정도로 생각하면 될 것 같다. Bra또, 이 Vector의 dual을 브라(bra)라고 하는데, \(\left|\psi\right>\)의 dual을 \(\left\)를 \(\begin{pmatrix} z_1\\ z_2\end{pmatrix}\)라고 두면, \(\left\)와 ..

문제 : http://codeforces.com/contest/854A. Fraction \(n \le 1000\)이기 때문에 다양한 풀이가 가능하다. 나는 생각을 최대한 안 하는 풀이인 Brute-force로 짰다. Complexity : \(O(n lg n)\) B. Maxim Buys an Apartment ㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷmin : 한 쪽에 아파트를 모두 몰아 놓았을 때이다. \(k=0 \vee k=n\)일 때 0, 아니면 1.max : 그리디하게 2,5,8,....번째 아파트를 inhabited로 설정해 주면 \(min(2k,n-k)\)이 최대가 됨을 쉽게 증명할 수 있는데, 코딩할 때 생각을 너무 안 해서 System Test에서 참교육을 당했다. 으아아아아아아아 Complexit..

stackexchange에서 본 내용. 페르마의 두 제곱수 정리에 의해, \(4k+1\)꼴의 소수는 두 제곱수의 합으로 표현이 가능하다. 이번엔 그 표현이 유일함을 보이자.기본적으로 꼴은 귀류. 1. Algebraic(?) NT\(p = a^2 + b^2 = c^2 + d^2 \)으로 표현될 수 있다고 하자. (\(\{a,b\}\neq\{c,d\}\)) 그럼 다음과 같이 \(p\)는 최소 4개의 서로 다른 가우스 소인수를 가진다. $$p = (a+bi)(a-bi) = (c+di)(c-di) $$그런데 가우스 정수의 집합 \(Z[i]\)는 Unique Factorization Domain이기 때문에,(*소인수 분해 꼴이 유일한 집합인 것 같다. 머수ㅡ알못이라 한참 후에야 추가가 가능할 듯하다) 이는 \(a..

문제 : 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..