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

[Verbery]

Может кто подскажет как поделить два разных числа представленных в виде разложения на простые числа и их степени?
Проблема возникла при вычислении биномиального коэффициента. Например при 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})...$. Ну это конечно если мы сможем биномиальный коэффициент представить в виде разложения простых чисел

[nnosipov]

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

можно выполнить следующее перемножение: $\varphi(n) = n(1- \frac{1}{p_1})(1-\frac{1}{p_2})...$.

Вам уже намекали, что $n$ может слишком большим. Поэтому с таким $n$ нужно работать "по кускам", целиком оно никуда не влезет.

[zykov]

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

Но вот как потом разделить оставшееся разложение $10\cdot9\cdot8\cdot7$ и ${4\cdot3\cdot2}$ не совсем ясно

Каждый из множителей разложить на простые множители, будет вектор степеней. Тогда для произведения вектора складываются. При делении из одного вектора вычитаем другой вектор.
(До $500000$ есть $41538$ простых чисел. Вот такими векторами и оперируйте.)

[mihaild]

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

Но вот как потом разделить оставшееся разложение $10\cdot9\cdot8\cdot7$ и ${4\cdot3\cdot2}$ не совсем ясно, ведь там может уже не оказаться общих простых чисел

Не может, ведь биномиальный коэффициент - целое число.

[Geen]

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

можно выполнить следующее перемножение: $\varphi(n) = n(1- \frac{1}{p_1})(1-\frac{1}{p_2})...$.

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

[zykov]

Geen в сообщении #1553801 писал(а):

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

Здесь можно, т.к. модуль - простое число и получается поле, т.е. можно делить по модулю.
Но во-первых, это несколько сложнее просто возведения в степень. Во-вторых, сама задача решается для любого модуля, не только простого. И алгоритм со степенями не изменится при замене модуля.

[Verbery]

Переделал по вашим рекомендациям, но где-то накосячил, так как на том же тесте теперь неверный ответ. Возможно где-то в другом месте нужно делить по модулю

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

 

[mihaild]

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

[slavav]

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 --

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

[Geen]

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

-- 03.05.2022, 15:35 --

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

Тут возможна проблема с неточным вычислением степени

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

[Verbery]

Geen
Для значений

n = 500_000

и

k = 250_000

выполняется 5987ms

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

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

[mihaild]

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

currCompositeNumber = i * j;

Вот тут оба сомножителя могут быть почти $2^{19}$.

[Geen]

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

выполняется 5987ms

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

(Оффтоп)

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

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

[Null]

return result * primeNmbr - primeNmbr;

Это такое умножение на $primeNmbr-1$?

[Verbery]

Извиняюсь, вчера вот только смог снова добраться до задачи. Согласно вашим рекомендациям подкорректировал программу, убрал листы, 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