포함 배제의 원리를 이용해 매우 큰 범위에서 조건에 맞는 수들만 빠르게 찾는 법 배우기 (+ 부분집합 구하기 재활)
1. 문제 9359번: 서로소 (acmicpc.net) 9359번: 서로소 첫째 줄에 테스트 케이스의 개수 T (0 < T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, A, B, N이 주어진다. (1 ≤ A ≤ B ≤ 1015, 1 ≤ N ≤ 109) www.acmicpc.net 2. 풀이 $10^{15}$이내에서 $N = 10^{9}$과 서로소인 수를 1초안에 찾으라고 한다면.. 보통의 방법으로는 찾기 힘들다 심지어 쿼리로 주어지니 더 어렵다 먼저 약수를 찾는 것보다 배수를 찾는 것이 쉽다는 것을 이해한다. N의 소인수를 모두 찾고, N의 소인수의 배수는 N과 서로소가 아니므로, 이 방법을 이용해 서로소가 아닌 수들을 찾는다. 범위 내에서 N과 서로소인 수와 서로소가 아닌 수로..
