https://www.acmicpc.net/problem/32632
문제요약
- 1 ~ N 노드(N 10^6)
- gcd(x,y)일때만 간선이 있음
- dist(x,y) = 두 정점 최단 경로 = 최단 간선의 개수
- 어떤 K에 대해서 dist(x,K) = gcd(x,K) 인 x의 개수 구하기
접근법
- K에서 BFS를 통해 모든 점까지의 거리를 구하고, 1 ~ N까지 모든점과의 GCD, 최단거리를 비교해서 접근하는 줄 알았음
- 하지만 시간이 너무 오래걸림 => 1000000과 서로소인 점의 개수는?
- 잘 생각해보면 모든 점들은 소수와 서로소이기 때문에 소수와 연결되어있을 것임(같은 경우는 제외하고)
- 1도 마찬가지
- 즉 서로소인 점들은 거리가 1, 그렇지 않은 점들도 최대 거리가 2
- 두 점의 gcd를 구해서 1이거나 2인 경우를 판단(K와 같은 경우는 제외하고)
newbieski