https://www.acmicpc.net/problem/23832
문제요약
- 1부터 N까지 정점이 있음(50000)
- 두 정점이 서로소이면 간선을 그릴 수 있음
- 얼마나 많은 간선이 필요한가
접근법
- 어떤 숫자와 소인수가 겹치지 않는 것의 개수를 찾아서 더하고 싶음
- 5만 이하의 숫자가 갖을 수 있는 서로 다른 소수의 개수는 6개
- 하나씩 구해보아도 되고
- 2 3 5 7 11 * 13 = 30030으로 추측도 가능함
- 어떤 수 x 에 대해서 x ~ N 사이에 조건을 만족하는 것들을 포함-배제로 구함
- 전체 개수 - 2의 배수인 것들 - 3의 배수인 것들 - ... + 2 3의 배수인 것들 + 3 5의 배수인 것들...
- N 2^6 6 = 50000 64 6 = 19,200,000
다른 접근법
- 오일러 피(파이) 함수
newbieski