취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16532번 문제인 Looking for the Risk Factor이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/16532 

먼저 2 이상 10만 이하의 수에 대해서 해당 수의 factor 중 가장 큰 factor를 구하자.

이는 int 배열에서 에라토스테네스의 체를 만들듯 2, 3, 5의 배수를 둘러보면서, 매 새로운 factor로 순회할 때 해당 수로 나눠지는 숫자들에 그 숫자를 덮어씌워 기록하는 작업을 하는 것으로 빠르게 구할 수 있다.

남은 일은 주어진 쿼리들을 K순으로 정렬한 뒤(offline query), K 이하가 최대 factor인 수들에 가중치 1을 모두 업데이트 한 뒤 구간합을 구하는 세그먼트트리를 관리하는 것으로 문제를 해결하는 것이다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int seg[262145];

int update(int L, int R, int qI, int sI) {
	if (qI < L || R < qI) return seg[sI];
	if (L == R) return seg[sI] = 1;
	return seg[sI] = update(L, (L + R) / 2, qI, sI * 2) + update((L + R) / 2 + 1, R, qI, sI * 2 + 1);
}

int rangesum(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return rangesum(L, (L + R) / 2, qL, qR, sI * 2) + rangesum((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

int sieve[100001];
vector<pair<int, int>> num; //가장큰primefactor, 원래수
vector<pair<pair<int, int>, int>> query; // {기준primefactor(K), 숫자}, 쿼리idx

int ans[100000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 2; i < 100000; i++) {
		if (sieve[i]) continue;
		for (int j = i * 2; j < 100001; j += i) {
			sieve[j] = i;
		}
	}
	for (int i = 2; i < 100001; i++) {
		if (sieve[i] == 0) num.emplace_back(make_pair(i, i));
		else num.emplace_back(make_pair(sieve[i], i));
	}

	sort(num.begin(), num.end());

	int Q; cin >> Q;
	for (int i = 0; i < Q; i++) {
		int N, K; cin >> N >> K;
		query.emplace_back(make_pair(make_pair(K, N), i));
	}
	
	sort(query.begin(), query.end());
	auto iter = num.begin();
	for (int i = 0; i < Q; i++) {
		while (iter != num.end()) {
			if ((*iter).first <= query[i].first.first) {
				update(1, 100000, (*iter).second, 1);
				iter++;
			}
			else break;
		}
		ans[query[i].second] = rangesum(1, 100000, 1, query[i].first.second, 1);
	}

	for (int i = 0; i < Q; i++) cout << ans[i] << '\n';
}