5

Ограничение по времени: 2 секунды.
Ограничение по памяти: 512 Мб.

Условие:

Даны две дроби a/b < c/d с целыми неотрицательными числителями и целыми положительными знаменателями, а также выбрано некоторое целое положительное N. Рассмотрим все несократимые дроби e/f с целыми положительными числителями и знаменателями, не превосходящими N, лежащие между этими двумя дробями: a/b < e/f < c/d . Выпишем их в конечную последовательность в порядке возрастания сначала знаменателей, а потом числителей: дробь e1/f1 будет в этом списке раньше e2/f2 , либо если f1 < f2, либо если f1 = f2 и e1 < e2. Ваша цель — вывести n первых дробей в этой последовательности (или всю последовательность, если в ней менее n дробей).

Формат входных данных:

В первой строке находятся шесть целых чисел a, b, c, d, N, n — две данные дроби, ограничение на числители и знаменатели и количество дробей, которые необходимо вывести (0 6 a 6 1018 , 1 <= b, c, d, N <= 1018 , 1 <= n <= 200 000). Гарантируется, что a b < c d.

Формат выходных данных:

В первой строке выведите целое число n' — количество дробей, которые вы выведете. В следующих n' строках выведите сами дроби в нужном порядке: в i-й строке должны быть целые ei и fi , разделённые пробелом — взаимно простые числитель и знаменатель i-й дроби (1 <= ei , fi <= N). Число n' должно либо равняться n, либо лежать в пределах от 0 до n − 1 и равняться количеству несократимых дробей между a b и c d , у которых числители и знаменатели целые положительные и не превосходят N.

Примеры:

Ввод: 0 1 1 1 5 10

Вывод:

9
1 2
1 3
2 3
1 4
3 4
1 5
2 5
3 5
4 5

Ввод: 55 34 68 42 90 1

Вывод:

1
89 55

Ввод: 49 33 45 30 50 239

Вывод:

0

Моё решение

Я использовал Дерево Штерна-Броко для генерации дробей.

Почему-то на большинстве тестов даёт Wrong Answer, на некоторых Time Limit.

#include <iostream>
#include <set>

using namespace std;

class fraction {
public:
    long long numerator, denominator;

    fraction() : numerator(0), denominator(0) {}

    fraction(long long numerator, long long denominator) : numerator(numerator), denominator(denominator) {}

    bool operator==(const fraction & fr) {
        return numerator == fr.numerator && denominator == fr.denominator;
    }

    bool operator!=(const fraction & fr) {
        return numerator != fr.numerator || denominator != fr.denominator;
    }
};

bool compare(const fraction& fr1, const fraction& fr2) { // для set
    if (fr1.denominator != fr2.denominator)
        return fr1.denominator < fr2.denominator;
    return fr1.numerator < fr2.numerator;
}

bool operator>(const fraction& fr1, const fraction& fr2) {
    if (fr1.denominator != fr2.denominator)
        return (double)fr1.numerator * fr2.denominator > (double)fr2.numerator * fr1.denominator;
    return fr1.numerator > fr2.numerator;
}

bool operator<(const fraction& fr1, const fraction& fr2) {
    if (fr1.denominator != fr2.denominator)
        return (double)fr1.numerator * fr2.denominator < (double)fr2.numerator* fr1.denominator;
    return fr1.numerator < fr2.numerator;
}

ostream& operator<<(ostream& str, const fraction& fr) {
    str << fr.numerator << ' ' << fr.denominator;
    return str;
}

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

int main() {

    long long a, b, c, d, N; int n;
    cin >> a >> b >> c >> d >> N >> n;

    {
        long long gcd1 = gcd(a, b), gcd2 = gcd(c, d);
        a /= gcd1, b /= gcd1;
        c /= gcd2, d /= gcd2;
    }

    set<fraction, decltype(&compare)> fractionSet(&compare);

    // два массива для генерации дерева
    fraction* arr1 = new fraction[262144];
    fraction* arr2 = new fraction[262144];

    int len1 = 3, i2 = 0; // индексы 1 и 2 показывают отношение к arr1 и arr2

    arr1[0] = fraction(0, 1), arr1[1] = fraction(1, 1), arr1[2] = fraction(1, 0);

    {
        // по окончании этого блока в arr1 остаётся две или больше дробей, причём первая дробь минимальна и больше a/b, вторая максимальна и меньше c/d, и все дроби между ними правильно сгенерированы
        fraction sample1 = fraction(a, b), sample2 = fraction(c, d);
    label:
        if (sample1 > arr1[1]) {
            arr1[0] = arr1[1];
            arr1[1] = fraction(arr1[0].numerator + arr1[2].numerator, arr1[0].denominator + arr1[2].denominator);
            goto label;
        }
        if (sample2 < arr1[len1-2]) {
            arr1[len1-1] = arr1[len1-2];
            arr1[len1-2] = fraction(arr1[len1-3].numerator + arr1[len1-1].numerator, arr1[len1-3].denominator + arr1[len1-1].denominator);
            goto label;
        }
        if (arr1[0] != sample1)
            if (arr1[1] != sample1)
                while (true) {
                    fraction fr = fraction(arr1[0].numerator + arr1[1].numerator, arr1[0].denominator + arr1[1].denominator);
                    if (fr.numerator > N || fr.denominator > N) {
                        len1--;
                        for (int i = 0; i < len1; i++)
                            arr1[i] = arr1[i+1];
                        break;
                    }
                    if (fr < sample1)
                        arr1[0] = fr;
                    else if (fr > sample1) {
                        for (int i = len1; i > 1; i--)
                            arr1[i] = arr1[i - 1];
                        len1++;
                        arr1[1] = fr;
                    } else {
                        arr1[0] = fr;
                        break;
                    }
                } else {
                    arr1[0] = arr1[1];
                    arr1[1] = arr1[2];
                    len1--;
                }
        int tmp = len1 - 2;
        if (arr1[tmp] != sample2) {
            while (true) {
                fraction fr = fraction(arr1[tmp].numerator + arr1[tmp+1].numerator, arr1[tmp].denominator + arr1[tmp+1].denominator);
                if (fr.numerator > N || fr.denominator > N) {
                    len1--;
                    break;
                }
                if (fr > sample2)
                    arr1[tmp + 1] = fr;
                else if (fr < sample2) {
                    arr1[len1] = arr1[len1 - 1];
                    len1++;
                    arr1[++tmp] = fr;
                } else {
                    arr1[++tmp] = fr;
                    break;
                }
            }
        } else
            len1--;
    }

    if (len1 < 2) {
        cout << 0 << endl;
        exit(0);
    }
    /*
        indexForRemove убирает дроби, после генерации которых получится дробь с числителем или знаменателем больше, чем N.
        Например, при N = 5 в последовательности 1/2 2/3 1/1 он уберёт только первую дробь.
        Возможно, не самое лучшее решение по производительности.
    */
    for (int i = 0, prevLen = 0, indexForRemove = 0;; i++) {
        for (int i1 = 0;; i1++) {
            arr2[i2] = arr1[i1];
            i2++;
            if (i1 + 1 == len1)
                break;
            long long numerator = arr1[i1].numerator + arr1[i1+1].numerator;
            if (numerator > N) {
                if (indexForRemove == i2 - 1)
                    indexForRemove++;
                continue;
            }
            long long denominator = arr1[i1].denominator + arr1[i1+1].denominator;
            if (denominator > N) {
                if (indexForRemove == i2 - 1)
                    indexForRemove++;
                continue;
            }
            fraction fr = fraction(numerator, denominator);
            arr2[i2] = fr;
            fractionSet.insert(fr);
            i2++;
        }
        if (indexForRemove != 0)
            memcpy(arr2, arr2 + indexForRemove, i2 -= indexForRemove);
        if (i2 < 2)
            break;
        fraction* tmp = arr1;
        arr1 = arr2;
        arr2 = tmp;
        len1 = i2;
        i2 = 0;
        prevLen = len1;
        indexForRemove = 0;
    }

    int limit = fractionSet.size() < n ? fractionSet.size() : n;

    cout << limit;
    set<fraction, decltype(&compare)>::iterator it = fractionSet.begin();
    for (int i = 0; i < limit; i++, it++)
        cout << '\n' << *it;
    cout << endl;
}

Вот вариант с перебором дробей. Практически все тесты опять WA, некоторые TL, правда, правильных ответов стало больше)
Может быть, я что-то упускаю?

int main() {

    long long a, b, c, d, N; int n;
    cin >> a >> b >> c >> d >> N >> n;

    long long* r = new long long[400'000];
    int pos = 0, i = a + 1, j = b;
    double f = (double)a / b, s = (double)c / d;

    while (n && j <= N) {
        int lim = min(N + 1, (long long)ceil(s * j));
        while (i < lim) {
            if (gcd(i, j) == 1) {
                r[pos++] = i;
                r[pos++] = j;
                if (--n == 0)
                    break;
            }
            i++;
        }
        i = ceil(f * ++j);
    }

    cout << pos / 2 << '\n';
    for (int i = 0; i < pos; i++) {
        cout << r[i] << ' ';
        cout << r[++i] << '\n';
    }
}
22
  • А может не химичить и сделать просто два цикла?
    – Qwertiy
    29 дек 2019 в 14:40
  • В чем, собственно, вопрос? 29 дек 2019 в 17:51
  • @MikhailIonkin Вопрос в том, как мне правильно решить задачу. 29 дек 2019 в 20:58
  • 1
    @Qwertiy попробовал. 30 дек 2019 в 19:42
  • 1
    @ИмяФамилия Как минимум у вас ошибка в выборе начального знаменателя, он может быть меньше b. Для 1 100 2 1 1000 10 первая дробь 1 1 а не 3 100
    – extrn
    31 дек 2019 в 0:37

1 ответ 1

1

Вам нужен быстрый алгоритм перечисления всех несократимых дробей с заданным знаменателем. Каждая такая дробь кодируется деревом Штерна-Броко

Сам ряд несократимых дробей это ряд Фарея. Вот пример генерации рядя Фарея с сайта geeksforgeeks.

Собственно приведенный код легко модифицировать под вашу задачу.

6
  • Эм.. Как это отвечает на вопрос, если именно это дерево и приведено в вопросе?
    – Qwertiy
    1 янв 2020 в 20:52
  • @qwertiy это наводит на мысль, что нужен ряд Фарея, а код реализации дерева с ошибками.
    – becouse
    1 янв 2020 в 21:05
  • Самое главное: автор не учитывает, что дробь может быть неправильная.
    – becouse
    1 янв 2020 в 21:09
  • Так в первом решении именно это я и делаю. 2 янв 2020 в 15:10
  • @ИмяФамилия, но дерево упорядочено по возрастанию дробей, а нужна другая сортировка.
    – Qwertiy
    2 янв 2020 в 15:41

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.