Функция Эйлера

[Verbery]

Здравствуйте, уважаемые форумчане! Не мог бы кто-нибудь помочь разобрать слабые места кода, где могут быть ошибки и что можно улучшить? Код проходит базовые тесты, но во время приёма программа падает на десятом тесте c "Ошибкой во время исполнения". Вот условие:

Цитата:

В этой задаче вам нужно вычислить значение функции Эйлера от некоторого биномиального коэффициента \begin{pmatrix} n \\ k\end{pmatrix} («выбрать k элементов из n»).

Формат ввода
В единственной строке записаны два целых числа k и n 0 ≤ k ≤ n ≤ 500 000

Формат вывода
Выведите одно число по модулю 1 000 000 007.

Пример 1
Ввод
1 5
Вывод
4
Пример 2
Ввод
0 2
Вывод
1
Пример 3
Ввод
5 10
Вывод
72

Вот моё решение на языке Java:

Используется синтаксис Java

import java.util.Scanner;

public class EulerFunAndBinomProblem {
    public long solution(int n, int k) {
        // диапазон множителей в числителе биноминального коэф. после сокращения
        int rangeForNumeratorFrom;
        // диапазон множителей в знаменателе биноминального коэф. после сокращения
        int rangeForDenominatorTo;
        if (n - k + 1 <= k) {
            rangeForNumeratorFrom = k + 1;
            rangeForDenominatorTo = n - k;
        } else {
            rangeForNumeratorFrom = n - k + 1;
            rangeForDenominatorTo = k;
        }

        long binomResult = rangeForNumeratorFrom > n ? 1 : 
                binomFunction(new int[] {rangeForNumeratorFrom, n}, new int[] {1, rangeForDenominatorTo});
        long result = 1;

        // перебираем все числа до binomResult и ищем те, у которых НОД равен 1
        for (int i = 2; i < binomResult; i++) {
            if (findGcd(binomResult, i) == 1) {
                result++;
            }
        }
        return result % 1_000_000_007;
    }

    private long binomFunction(int[] numeratorRange, int[] denominatorRange) {
        long numerator = 1;
        int from = numeratorRange[0];
        int to = numeratorRange[1];
        while (from <= to) {
            numerator *= from;
            from++;
        }

        long denominator = 1;
        from = denominatorRange[0];
        to = denominatorRange[1];
        while (from <= to) {
            denominator *= from;
            from++;
        }

        return numerator / denominator;
    }

    private long findGcd(long a, long b) {
        if (a % b == 0) {
            return b;
        }
        return findGcd(b, a % b);
    }

    // тут старт программы. Ввод данных через консоль
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int k = s.nextInt();
        int n = s.nextInt();

        EulerFunAndBinomProblem o = new EulerFunAndBinomProblem();
        System.out.println(o.solution(n, k));
    }
}
 

[mihaild]

Насколько я понимаю, вы пытаетесь посчитать сам коэффициент. Оцените примерно величину коэффициента при $n = 500000$, $k = 250000$.

[Lia]

Тема перемещена из форума «Олимпиадные задачи (CS)» в форум «Программирование»

[alisa-lebovski]

Просто получается слишком большое число. Надо сразу считать по модулю.

[nnosipov]

Сначала нужно от этого большого числа взять функцию Эйлера.

[Verbery]

Не подскажите как вообще решать такое для экстремально больших чисел типа $\begin{pmatrix} 500 000 \\ 250 000 \end{pmatrix}$? Гуглить длинную арифметику или есть какие-то хитрости?

Так же не понял фразу alisa-lebovski

Цитата:

Надо сразу считать по модулю.

Ведь если при вычислении биномиального коэф-та я на каждой итерации буду делать %1 000 000 007 то у меня из выйдет некорректное число

[nnosipov]

Verbery
А что такое функция Эйлера Вы знаете? Как вычисляются ее значения?

[Verbery]

nnosipov
Если обозначим ф-цию Эйлера за $f$, то $f(n)$ выдаёт взаимнопростые числа для n в диапазоне $(1, n)$. Это то, что я нагугливал про эту функцию.

Видно вы намекаете, что нужно посмотреть реализации алгоритма нахождения функции Эйлера..)

[nnosipov]

Verbery в сообщении #1553564 писал(а):

Если обозначим ф-цию Эйлера за $f$, то $f(n)$ выдаёт взаимнопростые числа для n в диапазоне $(1, n)$.

Не выдает, а считает их количество. В общем, просвещайтесь в вопросе вычисления значений функции Эйлера $\varphi(n)$ (это ее традиционное обозначение). Без решения этого вопроса никакой разумной программы написать нельзя.

[zykov]

Verbery в сообщении #1553536 писал(а):

Используется синтаксис Java

// перебираем все числа до binomResult и ищем те, у которых НОД равен 1
for (int i = 2; i < binomResult; i++) {
    if (findGcd(binomResult, i) == 1) {
        result++;
    }
}

Думаю, от Вас ожидали не такое решение "в лоб", а эффективное решение, тем более, что надо решать для больших значений.
Почитайте про функцию Эйлера.
Вам нужно её свойство мультипликативности.
Т.е. нужно её аргумент (этот биномиальный коэффициент) на простые множители разложить и из них получить значение функции Эйлера.

Длинная арифметика не нужна. Для этого и стоит в условии требование искать остаток, а не само длинное значение. Тут нужно все промежуточные вычисления (сложение и умножение) этого значения делать по этому модулю.

[slavav]

Функция Эйлера мультипликативна. Вам следует вычислить биномиальный коэффициент в виде разложения на простые множители. Понадобится представлять факториал в виде разложения на простые множители. Так же нужно уметь делить такие разложения друг на друга.

Понадобятся простые, которые можно получить с помощью решета Эратосфена.

Вычисление самой функции Эйлера по разложению надо делать по модулю. Вам понадобится быстрое возведение в степень по модулю.

P.S. Можно обойтись без быстрого возведения в степень. Всего несколько миллионов произведений по модулю - процессор стерпит.

[Vladimir-80]

А чем примечательно число 1 000 000 007? На ресурсе https://projecteuler.net/, где задачи заточены не только и не столько на программирование, сколько на математику, это число в этой же роли встречается нередко. Красивое, или за ним таится нечто большее?

-- 28.04.2022, 20:24 --

(Оффтоп)

Первое простое больше миллиарда?

[mihaild]

Vladimir-80 в сообщении #1553603 писал(а):

Первое простое больше миллиарда?

В первую очередь этим. Еще приятно что у него есть близнец.

[slavav]

Простое, легко запомнить, удвоенное значение помещается в int32_t.

[Geen]

slavav в сообщении #1553590 писал(а):

Вам понадобится быстрое возведение в степень
по модулю.

Строго говоря, ещё и умножение по модулю нужно.