Расчет 1^X + 2^X + ... + N^X mod 1000000007

Есть ли какой-либо алгоритм для вычисления (1^x + 2^x + 3^x + ... + n^x) mod 1000000007?
Примечание: a^b - это b-я степень.Расчет 1^X + 2^X + ... + N^X mod 1000000007

Ограничения: 1 <= n <= 10^16, 1 <= x <= 1000. Таким образом, значение N очень велико.

Я могу только решить для O(m log m) если m = 1000000007. Это очень медленно, потому что срок составляет 2 секунды.

У вас есть эффективный алгоритм?

Был комментарий, что он может быть дубликат this question, но это определенно отличается.

источник

2017-01-17 square1001

@TobySpeight Нет, это определенно отличается. 1^x, 2^x ..., n^x экспоненциально mod, и я хочу найти FAST ALGORITHM, потому что n <= 10^16 и mod = 10^9 + 7. – square1001

n^x mod m совпадает с ((n^(x-1) mod m) * (n mod m)) mod m; (a + b) mod m совпадает с ((mod m) + (b mod m)) mod m. – Vatine

@TobySpeight В моем медленном алгоритме я должен принять мод примерно 10^10 раз. Но это очень медленно, потому что ограничение времени составляет 2 секунды. Я только хочу найти быстрый алгоритм. – square1001

Вы можете суммируют серии

с помощью Faulhaber's formula и вы получите многочлен с X + 1 мощности для вычисления для произвольного N.

Если вы не хотите, чтобы вычислить чисел Бернулли, вы можете найти многочлен, решая X + 2линейных уравнений (для N = 1, N = 2, N = 3, ..., N = X + 2), который является медленным методом, но проще в реализации.

Приведем пример для X = 2. В этом случае мы имеем многочлен X + 1 = 3 порядка:

A*N**3 + B*N**2 + C*N + D

Линейные уравнения

 A + B + C + D = 1    = 1 
    A*8 + B*4 + C*2 + D = 1 + 4   = 5 
    A*27 + B*9 + C*3 + D = 1 + 4 + 9  = 14 
    A*64 + B*16 + C*4 + D = 1 + 4 + 9 + 16 = 30

Решив уравнения, мы получим

A = 1/3 
    B = 1/2 
    C = 1/6 
    D = 0

Заключительная формула

1**2 + 2**2 + ... + N**2 == N**3/3 + N**2/2 + N/6

Теперь вам нужно всего лишь поставить произвольное большоеN в формулу. До сих пор алгоритм имел сложность O(X**2) (поскольку он не зависит от N).

источник

2017-01-17 11:41:20

Но, к сожалению, x может быть 1000 ... Решение линейного уравнения может быть O (X^3), но я думаю, что оно медленное. Сейчас я проверяю Формулу Фаульхабера. – square1001

@ square1001: если вам нужно быть очень быстрым, я предлагаю предварительно вычислить * Bernoulli Numbers * (до '1000'); это непростая задача (например, решение линейных уравнений), но в этом случае вы получите почти полностью готовый полином. –

Я проверил номер Бернулли и, наконец, понял, что B [1], B [2], ..., B [x] для O (x^2). Поэтому эта проблема может решить для O (N^2)! – square1001

Существует несколько способов ускорения модульного возведения в степень. Отсюда я буду использовать ** для обозначения «экспоненциального» и % для обозначения «модуля».

Первые несколько наблюдений. Всегда бывает, что (a * b) % m - ((a % m) * (b % m)) % m. Также всегда бывает, что a ** n совпадает с (a ** floor(n/2)) * (a ** (n - floor(n/2)). Это означает, что для показателя < = 1000 мы всегда можем завершить возведение в не более 20 умножений (и 21 мода).

Мы также можем пропустить несколько расчетов, так как (a ** b) % m - это то же самое, что и ((a % m) ** b) % m, и если m значительно меньше n, мы просто имеем несколько повторяющихся сумм с «хвостом» частичного повторения.

источник

2017-01-17 11:19:04 Vatine

Но ваш алгоритм должен вычислить 1^x, 2^x, ..., 1000000006^x. Он имеет более 10^9 терминов, поэтому вам нужно повторять более 10^10 раз. Таким образом, я думаю, что это не может пройти, потому что срок составляет 2 секунды. – square1001

@ square1001 Просто протестировал петлю NOP на моем ноутбуке, занимает ~ 0,1 секунды, чтобы повторить 10 ** 10 раз, и это, вероятно, доминирует «fork» и «exec». – Vatine

Это становится намного проще, если * x * нечетно, потому что, например, '1000000006' соответствует' -1', поэтому '1^x' и' 1000000006^x' отменяются, и поэтому многие другие сроки. Я не вижу ярлыка, если * x * четный. –

Я думаю, что ответ Ватины - это, вероятно, путь, но я уже набрал , и это может быть полезно, для этого или для чужой аналогичной проблемы .

У меня нет времени этим утром для подробного ответа, но подумайте об этом. 1^2 + 2^2 + 3^2 + ... + n^2 принимает O (n) шаги для вычисления непосредственно. Однако он эквивалентен (n(n+1)(2n+1)/6), который может быть вычислен в O (1) раз. Аналогичная эквивалентность существует для любой более высокой интегральной мощности x.

Может возникнуть общее решение таких проблем; Я не знаю одного, , и Wolfram Alpha, похоже, тоже не знает об этом. Однако в общее эквивалентное выражение имеет степень x + 1 и может быть обработано , вычисляя некоторые значения выборки и решая набор линейных уравнений для коэффициентов линейного уравнения .

Однако, это было бы трудно для больших x, например 1000, как в вашей задаче , и, вероятно, не может быть сделано в течение 2 секунд.

Возможно, кто-то, кто знает больше математики, чем я, может превратить это в работоспособное решение ?

Редактировать: Упс, я вижу, что Фабиан Пиджке уже опубликовал полезную ссылку о Faulhaber's formula, прежде чем я разместил сообщение.

источник

2017-01-17 11:27:57

ответ

Смежные вопросы