모두 Happy New Year! ▣ 정수론 시리즈 ─ 순서대로 읽으시는 걸 추천합니다. 1. 뫼비우스 함수와 디리클레 합성곱 2. Double Counting과 Harmonic Lemma 3. 곱셈적 함수 테이블 만들기 4. Mertens Trick (xudyh's sieve) (현재 글) Intro 이번에도 문제 하나를 소개하면서 시작한다. Problem. 오일러 토션트 함수의 합 양의 정수 $N$이 주어질 때, 다음 식의 값을 1초 안에 구하는 프로그램을 작성하시오. (단, $N \le 10^9$이다.) $$S_{\phi}(N) = \sum_{n=1}^N \phi(n)$$ 이전 글에서 소개했듯이, 오일러 토션트 함수의 테이블을 $\mathcal O(N \log N)$에 채울 수 있으므로 $\phi(..
인접행렬과 인접리스트 $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, &..
- Total
- Today
- Yesterday