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

[mihaild]

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

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

Не понадобится, сумма всех степеней простых, входящих в $500000!$, меньше 2 миллионов.

[Geen]

mihaild в сообщении #1553686 писал(а):

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

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

Не понадобится, сумма всех степеней простых, входящих в $500000!$, меньше 2 миллионов.

Для двойки ведь и двух тысяч достаточно для переполнения...

[slavav]

Согласен mihaild, можно без быстрого возведения в степень.

Geen, последовательное перемножение по модулю решает проблему переполнения.

[Geen]

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

Согласен mihaild, можно без быстрого возведения в степень.

Geen, последовательное перемножение по модулю решает проблему переполнения.

Что-то я потерялся - это же как?
Двойку надо реально возводить в степень несколько тысяч. И простые числа порядка десятка тысяч надо возводить в степень порядка десятков.

[mihaild]

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

Двойку надо реально возводить в степень несколько тысяч.

Для этого нужно возведение в степень по модулю. Для этого не нужно быстрое возведение в степень.

[Geen]

mihaild в сообщении #1553696 писал(а):

Для этого нужно возведение в степень по модулю. Для этого не нужно быстрое возведение в степень.

Не понимаю. Допустим в однобайтной арифметике нам надо возвести 3 в десятую степень по модулю 101 - что предлагается?

[mihaild]

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

Допустим в однобайтной арифметике нам надо возвести 3 в десятую степень по модулю 101 - что предлагается?

Не получится, нужно чтобы модуль - 1, умноженный на основание степени, влезал в переменную. По модулю 83 - просто в цикле пишем x = (x * 3) % 83.

[Geen]

mihaild в сообщении #1553703 писал(а):

Не получится, нужно чтобы модуль - 1, умноженный на основание степени, влезал в переменную.

Так я и говорю, что ещё и умножение по модулю ("медленное") надо реализовать. И какой смысл умножать в цикле, если быстрое возведение в степень реализуется всего парой дополнительных строчек?

[slavav]

Geen, смысл в том чтобы снизить общую сложность первой реализации. Для решения задачи требуется изучить три-четыре новые для ТС вещи. Это много. Если можно обойтись без быстрого возведения, надо это сделать. Тут я согласен с mihaild.

[Geen]

slavav
Да, но умножение по модулю и быстрое возведение в степень - один и тот же алгоритм, по сути.

[mihaild]

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

умножение по модулю и быстрое возведение в степень - один и тот же алгоритм, по сути

Простите, каким образом?
Быстрое возведение в степень - это алгоритм, позволяющий вычислить $n$-ю степень относительно любой ассоциативной операции на $O(\log n)$ её применений (в отличии от наивного цикла за $\Theta(n)$).
Умножение по модулю - подсчет произведения в кольце вычетов, использующий что если в качестве представителей элементов $\mathbb Z_n$ брать числа $0, \ldots, n - 1$, то представитель произведение есть остаток от деления произведения представителей на $n$.
Я знаю, что вы написанное выше знаете, но не понимаю, как можно сказать что это "один и тот же алгоритм", я не вижу между ними вообще никакой связи.

[Geen]

mihaild в сообщении #1553722 писал(а):

как можно сказать что это "один и тот же алгоритм"

mihaild в сообщении #1553722 писал(а):

вычислить $n$-ю степень относительно любой ассоциативной операции на $O(\log n)$ её применений

Умножение это $n$-ая степень сложения.
А как иначе умножать по модулю? Например, как в примере выше, в однобайтной арифметике 3 умножить на 100 по модулю 101?

[mihaild]

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

А как иначе умножать по модулю?

А, я понял. Да, так можно реализовать умножение в случае, когда просто произведение сомножителей в арифметику не влезает (и мне это как-то в голову не приходило). Но в нашем случае это не нужно - нам доступна 64-битная арифметика, в которую влезает квадрат модуля.

[Geen]

mihaild в сообщении #1553724 писал(а):

Но в нашем случае это не нужно - нам доступна 64-битная арифметика, в которую влезает квадрат модуля.

Ну, а в JS, к примеру - нет
И язык, кстати, в стартовом сообщении не задан.

-- 01.05.2022, 12:24 --

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

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

Кстати, на JS сделал три вариации "расширения списка простых"....
Увы, "решето" победило

[mihaild]

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

Ну, а в JS, к примеру - нет

Там есть даблы с 53 битами, которых тоже хватит:)
ТС писал на джаве, так что она доступна, и в ней 64-битные числа наверняка есть.