남남서의 블로그

p가 소수일 때, p의 배수가 아닌 모든 a에 대해 ${ a }^{ p-1 }\equiv 1 \mod p$이다. 홀수 d에 대해 $p-1={ 2 }^{ s }\cdot d$이라고 하자. 이제 이렇게 쓸 수 있다. $$\Large{a^{2^{s} \cdot d} \equiv 1 \mod p}$$ s가 1 이상이라면 2를 하나 떼어낼 수 있다. $$\Large{ a^{2^{s} \cdot d} \equiv 1 \mod p \\ a^{2^{(s-1)} \cdot 2 \cdot d} \equiv 1 \mod p \\ a^{(2^{(s-1)} \cdot d) \cdot 2} \equiv 1 \mod p \\ \left(a^{2^{(s-1)} \cdot d}\right)^{2} \equiv 1 \mod p }$$ ..

algorithm이라는 헤더엔 std::sort() 라는 함수가 있습니다. 즉 #include 을 하고 using namespace std;를 하면 sort() 함수를 쓸 수 있습니다. sort() 함수는 크기가 커지는 순서대로 배열을 정렬하는 함수입니다. 예를 들어 [5, 1, 2, 4]가 있으면 [1, 2, 4, 5]가 되게 정렬하는 식이지요. a라는 배열의 i번째부터 j번째까지의 값을 정렬하고 싶을 땐 이렇게 씁니다. sort(a + i, a + j + 1);이렇게 하면 a[i]부터 a[j]까지(양쪽 경계 포함)의 값이 정렬되어 저장됩니다. 이 함수가 새로운 배열을 반환하는 것이 아니라, a 배열의 값이 바뀌게 됩니다. 첫 번째 인자로는 (범위의 시작점) 두 번째 인자로는 (범위의 끝점 + 1) 을..

구조체란 여러 변수를 묶어 하나로 쓰는 것이다. 다음 그림을 보자. 구조체를 만들 때는 struct 구조체이름 { 변수형 내부이름; 변수형 내부이름; ... 변수형 내부이름; }; 이런 식으로 선언한다. 안쪽의 변수형 내부이름;은 평소에 변수를 선언할 때처럼 쓰면 된다. 내부이름이 어떤 의미인지는 곧 알 수 있다. 구조체는 '설계도'와 같은 존재이다. 설계도가 있어도 그 설계도로 집을 지어야 비로소 그 안에서 살 수 있듯이, 구조체를 가지고 변수를 만들어야 비로소 그 값에 접근할 수 있다. 이 때 만들어진 변수는 당연히 구조체에 설계한 그대로 구조가 만들어진다. 구조체 이름이 asdf라면, 그 구조체를 가지고 x라는 이름의 변수를 만드려면 asdf x; 라고 선언하면 된다. int a; 와 똑같이 생각하..

König's theorem states : In a bipartite graph, (Maximum matching) = (Minimum vertex cover) 임의의 vertex cover는 모든 간선을 cover해야 한다. 임의의 matching은 일부의 간선을 cover한다. 따라서 vertex cover의 갯수는 항상 어떤 matching의 갯수보다 크거나 같다. (각각의 매칭된 간선에서 점을 하나씩 고른다고 생각해보자.) 즉 (Minimum vertex cover) ≥ (Maximum matching). 따라서 어떤 Maximum matching M에 대해서, 크기가 \(|M|\)인 vertex cover를 만든다면 그것이 최소일 것이다. 크기가 |M|인 vertex cover를 만드려면 일단..