Need not to know

▣ 문제 출처 ─ 제3회 kriiicon ㅅ번 문제 ▣ 알고리즘 분류 ─ 수학 / 구현 / 기하 / 많은 조건 분기 / 미적분학(그린 정리) ▣ solved.ac 기준 난이도 ─ Ruby II 문제 링크: https://www.acmicpc.net/problem/11392 약 한 달 전쯤, 모 세미나(?)에서 본 문제의 풀이에 대해 발표할 일이 있었어서 발표 자료를 만들었는데… 나름대로 열심히 만든 자료를 한 번 발표하는 데 쓰고 끝내기는 좀 아까워서 여기에도 올려봅니다! (파일 저장 후 '읽기 전용'으로 여시면 됩니다.) 원본 발표 자료에서 개인 정보나 문제 풀이와 관련 없는 부분 등을 조금 수정한 버전입니다. 이 문제를 도전하시는 분들에게 조금이라도 도움이 되셨으면 좋겠습니다. :) 덧붙여, 본 문제..

2020. 12. 07 ~ 2022. 06. 06 대한민국 육군 병장 만기전역 군 복무 끝!

▣ 문제 출처 ─ 제1 회 곰곰컵 G번 문제 ▣ 알고리즘 분류 ─ 수학 / 확률론(기댓값의 선형성) / 조합론(더블 카운팅) ▣ solved.ac 기준 난이도 ─ Gold II (개인적으로는 골1 정도라고 생각한다.) 문제 링크: https://www.acmicpc.net/problem/25197 $N$명의 사람들이 서로 다른 $K$개의 조에 균등한 확률로 랜덤하게 나뉘어 들어간다. 각 조에서 모든 쌍이 식사를 한 번씩 한다고 할 때, 전체 식사 횟수의 기댓값은 얼마일까? 일단 $N$명의 사람들이 $K$개의 조에 들어가는 모든 경우의 수는 $K^N$가지인 걸 알고 있으므로 총 식사 횟수의 합을 구할 수 있으면 되는데, 모든 경우에 대해 일일이 식사 횟수를 구하는 건 범위상 당연히 불가능하다. 그런데 어차..

모두 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(..

모두 메리 크리스마스! ▣ 정수론 시리즈 ─ 순서대로 읽으시는 걸 추천합니다. 1. 뫼비우스 함수와 디리클레 합성곱 2. Double Counting과 Harmonic Lemma 3. 곱셈적 함수 테이블 만들기 (현재 글) 4. Mertens Trick (xudyh's sieve) 「뫼비우스 함수와 디리클레 합성곱」 게시글에서 여러 곱셈적 함수들의 예시를 소개하였다. 본 글에서는, 곱셈적 함수들의 테이블을 만드는 코드들을 작성해 볼 것이다. 여기서 "함수의 테이블을 만든다"의 의미는 어떤 양의 정수 $N$과 함수 $f(n)$에 대해 $f(1)$, $f(2)$, $\cdots$, $f(N)$의 값을 모두 구한다는 의미이다. 양의 약수의 개수 $\tau(n)$ naive하게 $N$개의 값을 모두 구하면 $\..