2014 dxdy logo

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

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




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


20/02/12
153
Может кто подскажет как поделить два разных числа представленных в виде разложения на простые числа и их степени?
Проблема возникла при вычислении биномиального коэффициента. Например при n=10, k=4 имеем такую дробь: $\frac{10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2}{(6\cdot5\cdot4\cdot3\cdot2)\cdot(4\cdot3\cdot2)}$
Как сократить $10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2$ и ${6\cdot5\cdot4\cdot3\cdot2}$ вроде очевидно, просто вычитаю степени общих простых чисел этих двух факториалов. Но вот как потом разделить оставшееся разложение $10\cdot9\cdot8\cdot7$ и ${4\cdot3\cdot2}$ не совсем ясно, ведь там может уже не оказаться общих простых чисел

Так же не понял зачем что-то возводить в степень. Ведь для вычисления функции Эйлера, если нам известно разложение аргумента на простые числа: $n = p_1^{a_{1}} p_2^{a_{2}}...$ то можно выполнить следующее перемножение: $\varphi(n) = n(1- \frac{1}{p_1})(1-\frac{1}{p_2})...$. Ну это конечно если мы сможем биномиальный коэффициент представить в виде разложения простых чисел

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


20/12/10
8858
Verbery в сообщении #1553794 писал(а):
можно выполнить следующее перемножение: $\varphi(n) = n(1- \frac{1}{p_1})(1-\frac{1}{p_2})...$.
Вам уже намекали, что $n$ может слишком большим. Поэтому с таким $n$ нужно работать "по кускам", целиком оно никуда не влезет.

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение03.05.2022, 10:21 


18/09/21
1727
Verbery в сообщении #1553794 писал(а):
Но вот как потом разделить оставшееся разложение $10\cdot9\cdot8\cdot7$ и ${4\cdot3\cdot2}$ не совсем ясно
Каждый из множителей разложить на простые множители, будет вектор степеней. Тогда для произведения вектора складываются. При делении из одного вектора вычитаем другой вектор.
(До $500000$ есть $41538$ простых чисел. Вот такими векторами и оперируйте.)

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


16/07/14
8807
Цюрих
Verbery в сообщении #1553794 писал(а):
Но вот как потом разделить оставшееся разложение $10\cdot9\cdot8\cdot7$ и ${4\cdot3\cdot2}$ не совсем ясно, ведь там может уже не оказаться общих простых чисел
Не может, ведь биномиальный коэффициент - целое число.

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


01/09/13
4472
Verbery в сообщении #1553794 писал(а):
можно выполнить следующее перемножение: $\varphi(n) = n(1- \frac{1}{p_1})(1-\frac{1}{p_2})...$.

А Вы сможете это перемножение вычислить точно (даже для небольших $n$)?

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение03.05.2022, 11:02 


18/09/21
1727
Geen в сообщении #1553801 писал(а):
А Вы сможете это перемножение вычислить точно (даже для небольших $n$)?
Здесь можно, т.к. модуль - простое число и получается поле, т.е. можно делить по модулю.
Но во-первых, это несколько сложнее просто возведения в степень. Во-вторых, сама задача решается для любого модуля, не только простого. И алгоритм со степенями не изменится при замене модуля.

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


20/02/12
153
Переделал по вашим рекомендациям, но где-то накосячил, так как на том же тесте теперь неверный ответ. Возможно где-то в другом месте нужно делить по модулю
Код:
% 1_000_000_007
Я это делаю в методе
Код:
euler
при вычислении степени я после каждого умножения делю на 1_000_000_007:
Код:
result = result * primeNmbr % 1_000_000_007;


код: [ скачать ] [ спрятать ]
Используется синтаксис Java
import java.util.*;

public class EulerFunAndBinomProblem {

    public long solution(int n, int k) {
        if (k > n / 2) k = n - k;
        if (k == 0) return 1L;

        List<List<Long>> binomPrimesAndTheirPows = new ArrayList<>();
        for (Long prime : getAllPrimesBefore(n)) {
            List<Long> multiplierAndPow = getPowForBinomPrime(prime, n, k);
            if (multiplierAndPow.get(1) != 0) {
                binomPrimesAndTheirPows.add(multiplierAndPow);
            }
        }

        long result = 1;
        for (List<Long> primeAndPow : binomPrimesAndTheirPows) {
            result *= euler(primeAndPow.get(0), primeAndPow.get(1));
        }

        return result;
    }

    /**
     *
     * @param currPrime - простое число, для которого ищем степень в разложении биномиального коэф.
     * @param n
     * @param k
     * @return список из двух элементов, первый - само простое число, второй - его степень в разложении
     */

    private List<Long> getPowForBinomPrime(long currPrime, int n, int k) {
        long resultPow = 0;
        List<Long> resultPrimeAndPow = new ArrayList<>(2);
        for (int j = 1; Math.pow(currPrime, j) <= n; j++) {
            resultPow += (int) (n / Math.pow(currPrime, j)) -
                    (int) (k / Math.pow(currPrime, j)) -
                    (int) ((n - k) / Math.pow(currPrime, j));
        }
        resultPrimeAndPow.add(currPrime);
        resultPrimeAndPow.add(resultPow);
        return resultPrimeAndPow;
    }

    private List<Long> getAllPrimesBefore(int upperLimit) {
        // eratosthenes sieve method
        boolean[] numbers = new boolean[upperLimit + 1];
        List<Long> primeNmbrs = new ArrayList<>();

        int currCompositeNumber;
        for (int i = 2; i <= upperLimit; i++) {
            if (!numbers[i]) {
                primeNmbrs.add((long) i);
                for (int j = 2; j < upperLimit; j++) {
                    currCompositeNumber = i * j;
                    if (currCompositeNumber > 0 && currCompositeNumber <= upperLimit) {
                        numbers[currCompositeNumber] = true;
                    }
                }
            }
        }
        return primeNmbrs;
    }

    /**
     * Если primeNmbr — простое, pow — натуральное число, то \phi (p^a)=p^a-p^{a-1}.
     * @param primeNmbr простое число
     * @param pow степень primeNmbr
     * @return кол-во простых числе перед primeNmbr
     */

    private long euler(long primeNmbr, long pow) {
        if (pow == 0) {
            return 1;
        }
        if (pow == 1) {
            return primeNmbr - 1;
        }

        long result = primeNmbr;
        while (pow > 2) {
            result = result * primeNmbr % 1_000_000_007;
            pow--;
        }
        return result * primeNmbr - primeNmbr;
    }

    /**
     * Тут старт программы. Ввод данных через консоль
     */

    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: Функция Эйлера
Сообщение03.05.2022, 15:01 
Заслуженный участник
Аватара пользователя


16/07/14
8807
Цюрих
Как минимум и ответ надо считать по модулю, само значение может получиться большим. Плюс посмотрите внимательно на реализацию решета - у вас там если int 32-битный может быть переполнение.

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


26/05/14
981
Код:
result *= euler(primeAndPow.get(0), primeAndPow.get(1));
Нет извлечения модуля. Переполнение.

-- 03.05.2022, 15:07 --

Код:
Math.pow(currPrime, j)
Тут возможна проблема с неточным вычислением степени. Всю процедуру можно сделать только на целочисленных делениях.

-- 03.05.2022, 15:08 --

Код:
return result * primeNmbr - primeNmbr;
Тоже нужен модуль.

-- 03.05.2022, 15:10 --

Направление верное.

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


01/09/13
4472
Verbery
А у Вас там по времени выполнения/памяти нет проверок/лимитов? А то уж больно ужасный код...

-- 03.05.2022, 15:35 --

slavav в сообщении #1553811 писал(а):
Тут возможна проблема с неточным вычислением степени

Там основная проблема что это 4 раза вычисляется (хотя ни одного не надо)...

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


20/02/12
153
Geen
Для значений
Код:
n = 500_000
и
Код:
k = 250_000
выполняется 5987ms

Отвечая на вопрос про проверки по времени. Да, нужно до 3 секунд, но у меня там выпал "Wrong answer" на 10-м тесте

mihaild
В решете переполнений быть не должно, так как у нас n <= 500_000, а простые ищем до n

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


16/07/14
8807
Цюрих
Verbery в сообщении #1553808 писал(а):
currCompositeNumber = i * j;
Вот тут оба сомножителя могут быть почти $2^{19}$.

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


01/09/13
4472
Verbery в сообщении #1553815 писал(а):
выполняется 5987ms

Что-то оооочень долго...

(Оффтоп)

у меня в JS в IE11 на компе который был нормальным 5 лет назад в сто раз быстрее

Скажите, зачем Вы создаёте так много листов (и зачем создаёте хоть один)?

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


12/08/10
1650
Код:
return result * primeNmbr - primeNmbr;
Это такое умножение на $primeNmbr-1$?

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


20/02/12
153
Извиняюсь, вчера вот только смог снова добраться до задачи. Согласно вашим рекомендациям подкорректировал программу, убрал листы, Math.pow и по модулю везде обрезал, где надо. В итоге все тесты программа прошла, 15ms для n=500_000 и k=250_000. Вот конечный рабочий вариант:

код: [ скачать ] [ спрятать ]
Используется синтаксис Java
import java.util.*;

public class EulerFunAndBinomProblem {

    public long solution(int n, int k) {
        if (k > n / 2) k = n - k;
        if (k == 0) return 1L;

        boolean[] visitedNmbrs = new boolean[n + 1];
        long result = 1, powForCurrPrime = 0;
        long nmbrForFactorization;
        // в основе этого цикла метод решето Эратосфена
        for (int primeNmbr = 2; primeNmbr <= n; primeNmbr++) {
            if (!visitedNmbrs[primeNmbr]) {
                nmbrForFactorization = primeNmbr;
                while (nmbrForFactorization <= n) {
                    for (int i = 1; nmbrForFactorization * i % 1_000_000_007 <= n; i++) {
                        powForCurrPrime++;
                        // тут мы производим сокращение на k!
                        if (nmbrForFactorization * i % 1_000_000_007 <= k) {
                            powForCurrPrime--;
                        }
                        // тут мы производим сокращение на (n-k)!
                        if (nmbrForFactorization * i % 1_000_000_007 <= n - k) {
                            powForCurrPrime--;
                        }
                        // отмечаем числа, которые уже вошли в разложение
                        visitedNmbrs[(int) nmbrForFactorization * i % 1_000_000_007] = true;
                    }
                    nmbrForFactorization *= primeNmbr;
                }
                result = result * euler(primeNmbr, powForCurrPrime) % 1_000_000_007;
                powForCurrPrime = 0;
            }
        }
        return result;
    }

    /**
     * Если primeNmbr — простое, pow — натуральное число, то \phi (p^a)=p^a-p^{a-1}.
     * @param primeNmbr простое число
     * @param pow степень primeNmbr
     * @return кол-во простых числе перед primeNmbr
     */

    private long euler(long primeNmbr, long pow) {
        if (pow == 0) {
            return 1;
        }
        if (pow == 1) {
            return primeNmbr - 1;
        }

        long result = primeNmbr;
        while (pow > 2) {
            result = result * primeNmbr % 1_000_000_007;
            pow--;
        }
        return (result * primeNmbr) % 1_000_000_007 - result;
    }

    /**
     * Тут старт программы. Ввод данных через консоль
     */

    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));
    }
}

 


Так же отвечая на вопрос Null. Это формула $\varphi (p^a)=p^a-p^{a-1}$ и я там допустил ошибку, надо было так:
Код:
(result * primeNmbr) - result

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

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



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

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


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

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