Я прочитал метод, приведенный в вашей ссылке, и принятое C ++ решение. Позвольте мне опубликовать их, для справки:
От редакции
Существует несколько неоптимальных решений. Используя приоритетную очередь, один
можно перебирать дроби (генерируя их одну за другой) в O (K
журнал N) время. Используя более сложное математическое отношение, это можно уменьшить до
ХОРОШО). Однако ни одно из этих решений не набирает много очков, потому что
число дробей (и, следовательно, K) является квадратичным в N.
«Хорошее» решение основано на метабинарном поиске. Чтобы построить это
Решение, нам нужна следующая подпрограмма: заданная дробь A / B
(что не обязательно является неснижаемым), найдите, сколько фракций из
Последовательность Фарея меньше, чем эта фракция. Предположим, у нас было это
подпрограмма; тогда алгоритм работает следующим образом:
- Определите число X так, чтобы ответ находился между X / N и (X + 1) / N; такое число можно определить с помощью двоичного поиска в диапазоне
1 ... N, таким образом вызывая подпрограмму O (log N) раз.
- Составьте список всех фракций A / B в диапазоне X / N ... (X + 1) / N. Для любого данного B в этом диапазоне находится не более одного A, и это может быть
определяется тривиально в O (1).
- Определите соответствующую статистику заказа в этом списке (достаточно выполнить сортировку в O (N log N) путем сортировки).
Осталось показать, как мы можем построить желаемую подпрограмму. Мы
покажет, как это может быть реализовано в O (N log N), тем самым давая O (N
log ^ 2 N) алгоритм общий. Обозначим через C [j] число
неприводимые дроби i / j, которые меньше X / N. Алгоритм
на основании следующего наблюдения: C [j] = этаж (X * B / N) - сумма (C [D],
где D делит j). Прямая реализация, которая проверяет, есть ли D
является делителем, дает квадратичный алгоритм. Лучший подход,
Вдохновленный ситой Эратосфена, заключается в следующем: на шаге j мы знаем
C [j], и мы вычитаем его из всех кратных j. Время работы
подпрограмма становится O (N log N).
Соответствующий код
#include <cassert>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const int kMaxN = 2e5;
typedef int int32;
typedef long long int64_x;
// #define int __int128_t
// #define int64 __int128_t
typedef long long int64;
int64 count_less(int a, int n) {
vector<int> counter(n + 1, 0);
for (int i = 2; i <= n; i += 1) {
counter[i] = min(1LL * (i - 1), 1LL * i * a / n);
}
int64 result = 0;
for (int i = 2; i <= n; i += 1) {
for (int j = 2 * i; j <= n; j += i) {
counter[j] -= counter[i];
}
result += counter[i];
}
return result;
}
int32 main() {
// ifstream cin("farey.in");
// ofstream cout("farey.out");
int64_x n, k; cin >> n >> k;
assert(1 <= n);
assert(n <= kMaxN);
assert(1 <= k);
assert(k <= count_less(n, n));
int up = 0;
for (int p = 29; p >= 0; p -= 1) {
if ((1 << p) + up > n)
continue;
if (count_less((1 << p) + up, n) < k) {
up += (1 << p);
}
}
k -= count_less(up, n);
vector<pair<int, int>> elements;
for (int i = 1; i <= n; i += 1) {
int b = i;
// find a such that up/n < a / b and a / b <= (up+1) / n
int a = 1LL * (up + 1) * b / n;
if (1LL * up * b < 1LL * a * n) {
} else {
continue;
}
if (1LL * a * n <= 1LL * (up + 1) * b) {
} else {
continue;
}
if (__gcd(a, b) != 1) {
continue;
}
elements.push_back({a, b});
}
sort(elements.begin(), elements.end(),
[](const pair<int, int>& lhs, const pair<int, int>& rhs) -> bool {
return 1LL * lhs.first * rhs.second < 1LL * rhs.first * lhs.second;
});
cout << (int64_x)elements[k - 1].first << ' ' << (int64_x)elements[k - 1].second << '\n';
return 0;
}
Основная методология
Приведенное выше редакционное объяснение приводит к следующей упрощенной версии. Позвольте мне начать с примера.
Допустим, мы хотим найти 7-й элемент последовательности Фареи с N = 5.
- Мы начнем с написания подпрограммы, как сказано в объяснении, которая дает нам значение «k» (сколько дробных чисел с уменьшенной последовательностью Фарея существует до заданной дроби - данное число может или не может быть уменьшено)
Итак, возьмите вашу последовательность F5:
k = 0, 0/1
k = 1, 1/5
k = 2, 1/4
k = 3, 1/3
k = 4, 2/5
k = 5, 1/2
k = 6, 3/5
k = 7, 2/3
k = 8, 3/4
k = 9, 4/5
k = 10, 1/1
Если мы можем найти функцию, которая находит количество предыдущих сокращенных дробей в последовательности Фаре, мы можем сделать следующее:
int64 k_count_2 = count_less(2, 5); // result = 4
int64 k_count_3 = count_less(3, 5); // result = 6
int64 k_count_4 = count_less(4, 5); // result = 9
Эта функция записана в принятом решении. Он использует точную методологию, описанную в последнем абзаце редакционной статьи.
Как видите, функция count_less() генерирует те же значения k, что и в нашем рукописном списке.
Мы знаем значения приведенных дробей для k = 4, 6, 9, используя эту функцию. А как насчет к = 7? Как объяснено в редакционной статье, мы перечислим все сокращенные дроби в диапазоне X / N и (X + 1) / N , здесь X = 3 и N = 5.
Используя функцию в принятом решении (в ее нижней части), мы перечисляем и сортируем сокращенные дроби.
После этого мы переставим наши значения k, чтобы они соответствовали нашему новому массиву следующим образом:
k = -, 0/1
k = -, 1/5
k = -, 1/4
k = -, 1/3
k = -, 2/5
k = -, 1/2
k = -, 3/5 <-|
k = 0, 2/3 | We list and sort the possible reduced fractions
k = 1, 3/4 | in between these numbers
k = -, 4/5 <-|
k = -, 1/1
(Вот почему есть этот фрагмент кода: k -= count_less(up, n);, он в основном переопределяет значения k)
(И мы также вычитаем еще один во время индексации, то есть: cout << (int64_x)elements[k - 1].first << ' ' << (int64_x)elements[k - 1].second << '\n';. Это просто для того, чтобы просто вызвать правильную позицию в сгенерированном массиве.)
Итак, для наших новых переназначенных значений k, для N = 5 и k = 7 (исходное значение k), наш результат равен 2 / 3.
(Мы выбираем значение k = 0 на нашей новой карте)
ЕслиВы компилируете и запускаете принятое решение, оно даст вам следующее:
Input: 5 7 (Enter)
Output: 2 3
Я полагаю, что это основной пункт редакционного и принятого решения.