📝 문제 정보#
🧐 관찰 및 접근#
- $R(n)$의 길이는 몇일까?
- $R(1) = 2$이고, $R(k) = R(k-1) + k$와 서로소인 자연수의 개수 인 것 같다.
- 오일러 피함수의 부분합 개수랑 같다.
- 암튼 나이브하게 돌려보니, 7600459개가 나온다. 이걸 0.5초안에 이걸 정렬하고 찾을?수?있을까? ㅋㅋ
- 수열이 좌우로 대칭인걸 고려하면 380만개정도만 정렬해도 될거같긴 한데… 그래도 빡세보인다. 0.5초라서
- $R(1) = 2$이고, $R(k) = R(k-1) + k$와 서로소인 자연수의 개수 인 것 같다.
- 흠.. 답에 대한 이분탐색이 될까? 사실 깔끔하게 이분탐색 하기 위해선, 정수조건으로 바꾸려면 1~5000의 LCM을 구해야 한다.. 진짜 개에바
- $10^{-4}$에 대한 정밀도까지만 하면 되지 않을까? 해봤자 가장 작은 수는 $\frac{1}{5000}$이니까… 라기엔 두 분수의 차는 결국 더 빡세지네. 해봤자 $\frac{1}{5000*4999}$인거같긴 한데…
- 아니 잠깐만, 생각해보니까 1~5000에 대해서 따로 정렬하면 시간복잡도가 꽤나 줄어드는것같다. 이렇게 해서 답에 대한 이분탐색을 해볼까..?
- 다 실패하고, nth_element와 short와 pragma Ofast와 Clang까지 섞은 최적화로 풀엇다… 하 이게 뭐하는 문제냐 ㄱ-
- 헉, 앞에 최대공약수를 구하는 부분을 반복문으로 전처리하면 훨씬 빠르게 돈다. 거기가 병목이었다니
💻 풀이#
- 코드 (C++):
void solve(){
int N, K; cin >> N >> K;
vector<pair<short,short>> v;
v.reserve(N * N / 2);
v.push_back({0, 1});
v.push_back({1, 1});
rep(i, 1, N+1) rep(j, i+1, N+1){
if(__gcd(i, j) != 1) continue;
v.push_back({(short)i, (short)j});
}
int sz = (int)v.size();
if(K*2 > sz){
K = sz - K + 1;
nth_element(v.begin(), v.begin() + K - 1, v.end(), [](auto& a, auto& b){
return a.first * b.second > a.second * b.first;
});
} else {
nth_element(v.begin(), v.begin() + K - 1, v.end(), [](auto& a, auto& b){
return a.first * b.second < a.second * b.first;
});
}
cout << v[K-1].first << " " << v[K-1].second << '\n';
}