Need not to know

※ 이 글을 읽기 전에, 제가 2년도 더 전에 타 블로그에서 썼던 글을 먼저 읽고 오시면 더 좋습니다. ▣ 정수론 시리즈 ─ 순서대로 읽으시는 걸 추천합니다. 1. 뫼비우스 함수와 디리클레 합성곱 2. Double Counting과 Harmonic Lemma (현재 글) 3. 곱셈적 함수 테이블 만들기 4. Mertens Trick (xudyh's sieve) Intro 이번 글은 문제 하나를 소개하며 시작하고자 한다. 2019년도 NYPC에서 다음과 같은 문제가 출제된 적이 있었다. NYPC 2019 Day 2 - 9번. 약수 문제 두 자연수 $a$, $b$가 주어질 때, $a$ 이상 $b$ 이하의 모든 양의 정수의 약수의 개수의 합을 구하시오. 다시 말해, $\sum\limits _{n=a}^{b} ..

※ 앞으로 몇 개의 게시글에 걸쳐, 비슷한 주제로 글을 쓸 예정입니다. ▣ 정수론 시리즈 ─ 순서대로 읽으시는 걸 추천합니다.1. 뫼비우스 함수와 디리클레 합성곱 (현재 글)2. Double Counting과 Harmonic Lemma3. 곱셈적 함수 테이블 만들기4. Mertens Trick (xudyh's sieve) Preliminaries and Notations  정수론에서 다루는 대상 중 수론적 함수(산술적 함수, Arithmetic Function)라는 것이 있다. 모든 양의 정수에 대해 정의된 복소함수를 일컫는데, 쉽게 말해서 수열을 의미한다. 그리고 수론적 함수 중에서도 조금 더 특별한 아이들을 모아 따로 부르는 명칭이 있으니, 그것이 바로 곱셈적 함수(Multiplicative Func..

▣ 문제 출처 ─ Polish Olympiad in Informatics(POI) 2005/2006 Stage 1의 5번 문제 ▣ 알고리즘 분류 ─ DFS / 이분 탐색 / 스위핑 / 기하 / CHT(Convex Hull Trick) ▣ solved.ac 기준 난이도 ─ Diamond IV (개인적으로는 다3 정도라고 생각한다.) 문제 링크: https://www.acmicpc.net/problem/1909 크기 $S = W_x \times W_y$ 그리드에 $n$개의 '특별한 점'이 주어진다. $(sx,\, sy)$에서 $(tx,\, ty)$로 가는 임의의 경로에 대해, 경로상의 임의의 점과 특별한 점들 사이 거리의 최솟값을 최대화하는 문제다. 일단 최솟값을 최대화하는 건 나중에 생각하기로 하고, 문제..

인접행렬과 인접리스트 $V$개의 정점이 있고 $E$개의 간선(방향이든 무방향이든 상관없지만, 여기서는 편의를 위해 무방향이라 가정하자)이 있는 그래프 $G(V,\, E)$를 생각하자. 이러한 그래프를 저장하는 방법은 크게 두 가지가 있다. 첫 번째는 인접행렬(Adjacency Matrix)이다. 어떤 두 점이 인접한지, 즉 두 점 사이에 간선이 있는지를 표시하는 행렬로 그래프를 표현한다. 실제 프로그래밍에서는 아래 코드와 같이 $V \times V$ 크기의 배열 g를 사용해서 g[A][B] 값을 A번 정점과 B번 정점 사이 간선의 개수로 저장한다. #include #define NMAX 1000 int g[NMAX][NMAX]; int main() { int N, M; scanf("%d%d", &N, &..

▣ 문제 출처 ─ 2019년도 서울대학교 프로그래밍 경시대회(SNUPC) Div. 1 G번 문제 ▣ 알고리즘 분류 ─ 수학(미적분학, 기하학, 확률론) ▣ solved.ac 기준 난이도 ─ Diamond II 문제의 내용은 여기에서 볼 수 있다. 필요하지 않은 스토리텔링 부분을 제외하면 문제의 내용은 한 줄로 요약할 수 있다: 다각형이 주어질 때, 다각형 내의 임의의 두 점 사이 거리의 제곱의 기댓값을 구하는 것이 목표다. 다각형 내의 점은 연속적으로 분포하므로 적분을 써야한다는 것을 쉽게 짐작할 수 있다. 주어지는 다각형의 전체 넓이(혹은 다각형 그 자체)를 $S$라고 하자. 두 점의 좌표를 각각 $(x_1,\, y_1),\, (x_2,\, y_2)$라 하면 거리의 제곱은 $(x_1 - x_2)^2 +..