number-theory

-1зной

1ответ

четырехквадратное представление суммы для целых чисел до N

Lagrange's four-square theorem доказывает, что любое натуральное число можно записать в виде суммы четырех квадратных чисел. Мне нужно найти любой способ написать натуральное число x как сумму четырех

3зной

1ответ

Какова наилучшая временная сложность, чтобы найти решение x^2 + y^2 = m, где m может быть любым натуральным числом?

Я должен найти решение уравнения x + y = m где m может быть любым натуральным числом, а x, y - целыми числами. Это можно сделать в O (m 1/2), легко используя грубую силу. Есть ли способ, которым я мог

-2зной

1ответ

почему 1 вычитается из мод, где мод = 1000000007 в расчете

ссылка вопроса http://codeforces.com/contest/615/problem/D звено раствора http://codeforces.com/contest/615/submission/15260890 В ниже коде я не могу понять, почему 1 вычитается из мод где мод = 10000

19зной

3ответ

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

Есть ли какой-либо алгоритм для вычисления (1^x + 2^x + 3^x + ... + n^x) mod 1000000007? Примечание: a^b - это b-я степень. Ограничения: 1 <= n <= 10^16, 1 <= x <= 1000. Таким образом, значение N очен

3зной

2ответ

Как найти все способы получения целого числа n в виде суммы m целых чисел (без порядка)?

Я ищу алгоритм, который находит все способы выразить целое число n как сумму m (неотрицательных) целых чисел. Меня особенно интересуют m = 6 и n⩽20. Какой бы самый быстрый способ найти все возможности

1зной

1ответ

Диапазон значений неподписанного qword (64-бит) с использованием меньших бит?

Я ищу способ представления диапазона значений: 0 - 18446744073709551615 с использованием менее 8 байт. Я попытался придумать, как это можно сделать, но ничего не работает. В теории, например: Использо

0зной

2ответ

Как найти максимальное связующее дерево в полном графике

Учитывая массив n положительных целых чисел, как мы можем найти максимальное остовное дерево в полном графике, учитывая вес края (i, j) = gcd(a[i], a[j])? Я знаю одно решение со сложностью O(n^2), но

0зной

1ответ

Максимальная сумма коэффициентов чисел в заданном диапазоне

Это вопрос, который я делал на какой-то платформе онлайн-судей. Найти максимальную сумму коэффициентов чисел от 1 до N. Например, если N должны были быть 11, то ответ будет 18. Число с наибольшей сумм