나만 몰라
문제를 풀다보면 분명 쉬운 아이디어인 것 같은데 나만 모르는게 있다. 맨날 당하니까 당할때마다 적으려고 한다.
정수론
서로소의 곱
a가 c랑 서로소이면서 b가 c랑 서로소이다. a * b와 c는 서로소이다. 두 문장은 필요충분조건이다.
https://codeforces.com/contest/1749/problem/D 이 문제를 풀다가 마지막에 a랑 b가 동시에 c랑 서로소면 m안에서 개수를 어떻게 셀지를 한참 고민하다 에디토리얼을 봤는데 너무 당연한 아이디어였다.
서로소의 개수
M이랑 [a, b]구간에 있는 서로소의 개수를 구하는 방법은 포함 배제의 원리로 가능하다.