0. Introduction

PS를 위한 정수론 가이드를 쓰기로 했다. 이유는 여러 가지.

• 자료가 부족하다는 의견을 많이 듣고, 동의함
• kipa00님의 NTA가 매우 좋은 자료인 것은 맞지만, 진입장벽이 상당하다
• 수학적 직관이나 엄밀한 증명을 일부 포기하더라도 내용을 간결하게 전달하는 것이 필요한 것 같다
• (나중에 직관/증명이 필요하다면, 그 때 직접 자료를 찾으면 된다. 처음 들이박는 것보다 쉬울 것)
• 그래서 최대한 문제 풀이에 집중하는 가이드가 필요하다고 생각했다
• 그러나, 각 알고리즘의 기본 원리 정도는 배우고 갈 수 있도록 내용을 작성하였다.
• (목표는 PS 정수론을 입문하기 위해 책을 폈다가 수학적 귀납법부터 시작하면서 의지를 잃는 사람들을 배려하는 것) 

이론 설명은 여기에 간단하게 하고, 관련 코드를 github에 올릴 계획. git 연습도 해야하니. 

연습문제도 올릴 예정인데, 이건 천천히 할 생각이다. 초반 주제들은 solved.ac에 관련 태그가 많으니 활용하자.

글을 읽다보면 뭔가 논리에 빈 공간이 있다는 생각이 들 수도 있다. 정수론 책을 그대로 옮기고 싶지 않아서 그런 것이다.

논리의 허점에 아쉬움을 느끼는 때가 오면, 학부용 정수론 책을 사서 읽으면 도움이 될 것이다. 위에서도 말했지만..

(+ 당연한거지만 학부 정수론을 모르는 상태로 어려운 문제를 풀려고 하면 한계가 올 것이다. 그때 필요하면 책을 읽으면 된다. 앞 몇 장만 읽어도 도움된다.)

일단 내용을 최대한 빠르게 퀄리티 신경 안 쓰면서 뽑아내고, 지적이나 제안을 받아가면서 천천히 보완할 생각이다. 

한 번에 완벽한 자료를 만들려고 하면 한 3~4단원하고 접을 가능성이 99.9%라서인데 사실 이게 더 나을수도 ㅋㅋㅋㅋ

가끔 오개념을 글에 쓰고 난 다음 나중에 고치는 일이 생길 수 있어, 글이 올라온 뒤 조금 시간이 지난 다음 읽는 것을 추천한다.

추가적으로 해야하는 언급들

• 시간복잡도 분석은 빡빡하게 하지 않을 것이다. 본격적으로 시간복잡도를 논의하려면 정수 덧셈도 로그 시간이라는 내용들을 녹여내야한다. 하지만 PS/CP에서 이렇게 시간복잡도를 분석하는 경우는 흔치 않으니, 여기서도 모든 덧셈과 곱셈은 $\mathcal{O}(1)$ 연산이라는 것으로 합의하자. 
• 비슷하게, $\mathcal{O}$ notation도 꽤 편안하게 (엄밀하지 않게) 사용할 것이다. 적당히 이해하고 넘어가자 :)
• 자료 수정/추가는 가끔 오류가 보이거나 필요가 생기면 할 것이다. github에서도 수정이 많을 수 있다.
• github에 올라온 코드는 팀노트에 복붙해서 넣을 퀄리티가 아니라, proof of concept 정도로 보는 것이 나을 것이다.

solved.ac 기준. 1~3 및 5 초반은 플레 중하위권 이하, 4, 5 후반은 플레 중상위권, 6번은 플레, 7, 8은 플레 상위권, 9~11번은 다이아 이상.

예상 커리큘럼

1. 기본기 잡기
2. 유클리드, 확장 유클리드 알고리즘
3. 중국인의 나머지 정리
4. 페르마 소정리, 오일러 정리 및 활용
5. 팩토리얼과 이항계수
6. Miller-Rabin 소수 판별 알고리즘과 Pollard-Rho 소인수분해
7. Mobius function과 그 활용
8. 원시근, 이산로그, 이산제곱근
9. 유클리드 알고리즘의 활용
10. 소수의 개수 빠르게 세기
11. more on multiplicative functions
12. 개인적인 후기, 그리고 그 이후의 이야기

1단원은 이미 자료가 많은 부분을 다루어, 덜 친절할 예정이다. 이 부분은 다른 자료를 찾는 것을 추천한다.

UPD: 백준 문제집 - 6593번 ~ 6603번

질문은 댓글로 항상 환영 :) (나도 내가 설명을 쉽게 못하는 사람인 걸 안다)