BOJ 25921 - 건너 아는 사이
MST문제처럼 보이지만 에라토스테네스의 체를 써서 푸는 문제이다.
의 배수는 모두 와 친구가 되는것이 이득이다.
가 가장 작은 서로소가 아닌 소인수이기 때문이다.
마찬가지로 의 배수 중에서도 의 배수가 아닌것들은 과 이어주고 쭉 해주면 된다.
그리고 각 소수들은 과 이어주어야 하므로 소수들도 정답에 더한다.
void solve() {
int n, ans = 0;
cin >> n;
vi used(n + 1);
for (int i = 2; i <= n; i++) {
if (!used[i]) {
used[i] = 1;
ans += i;
for (int j = i * 2; j <= n; j += i) {
if (!used[j]) {
ans += i;
used[j] = 1;
}
}
}
}
cout << ans;
}
Comments