2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Функция Эйлера
Сообщение27.04.2022, 17:50 
Аватара пользователя


20/02/12
135
Здравствуйте, уважаемые форумчане! Не мог бы кто-нибудь помочь разобрать слабые места кода, где могут быть ошибки и что можно улучшить? Код проходит базовые тесты, но во время приёма программа падает на десятом тесте 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));
    }
}
 

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение27.04.2022, 18:03 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Posted automatically
Сообщение27.04.2022, 18:12 


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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение27.04.2022, 21:35 
Заслуженный участник
Аватара пользователя


05/12/09
1760
Москва
Просто получается слишком большое число. Надо сразу считать по модулю.

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение27.04.2022, 22:06 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение28.04.2022, 06:26 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение28.04.2022, 06:34 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение28.04.2022, 06:57 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение28.04.2022, 07:31 
Заслуженный участник


20/12/10
8858
Verbery в сообщении #1553564 писал(а):
Если обозначим ф-цию Эйлера за $f$, то $f(n)$ выдаёт взаимнопростые числа для n в диапазоне $(1, n)$.
Не выдает, а считает их количество. В общем, просвещайтесь в вопросе вычисления значений функции Эйлера $\varphi(n)$ (это ее традиционное обозначение). Без решения этого вопроса никакой разумной программы написать нельзя.

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение28.04.2022, 08:29 


18/09/21
1676
Verbery в сообщении #1553536 писал(а):
Используется синтаксис Java
// перебираем все числа до binomResult и ищем те, у которых НОД равен 1
for (int i = 2; i < binomResult; i++) {
    if (findGcd(binomResult, i) == 1) {
        result++;
    }
}
Думаю, от Вас ожидали не такое решение "в лоб", а эффективное решение, тем более, что надо решать для больших значений.
Почитайте про функцию Эйлера.
Вам нужно её свойство мультипликативности.
Т.е. нужно её аргумент (этот биномиальный коэффициент) на простые множители разложить и из них получить значение функции Эйлера.

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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение28.04.2022, 16:01 
Заслуженный участник


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

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

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

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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение28.04.2022, 20:23 
Заблокирован


19/02/13

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

-- 28.04.2022, 20:24 --

(Оффтоп)

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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение28.04.2022, 20:51 
Заслуженный участник
Аватара пользователя


16/07/14
8344
Цюрих
Vladimir-80 в сообщении #1553603 писал(а):
Первое простое больше миллиарда?
В первую очередь этим. Еще приятно что у него есть близнец.

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение28.04.2022, 20:58 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение30.04.2022, 15:57 
Заслуженный участник
Аватара пользователя


01/09/13
4318
slavav в сообщении #1553590 писал(а):
Вам понадобится быстрое возведение в степень
по модулю.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 60 ]  На страницу 1, 2, 3, 4  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group