Алгоритм теории чисел

Дайте два положительных целого числа a, b (1 <= a <= 30, 1 <= b <= 10000000) и определите два неповторимых набора L и R,

L = {x * y | 1 <= x <= a, 1 <= y <= b, x,y is integer}

R = {x ^ y | 1 <= x <= a, 1 <= y <= b, x,y is integer},

^ работает XOR

Для любых двух целых чисел: A∈L, B∈R, отформатируем B до n + 1 (n - десятичное число из числа b) десятичной цифры (заполните 0 перед B), а затем соедините B с конец A и получить новое целое AB.

Вычислить сумму всего порожденного целого AB (если сумма превышает, просто верните "sum mod 1000000007", mod означает модульную операцию)

Примечание: время вашего алгоритма не более 3 секунд

Мой алгоритм очень прост: мы можем легко получить максимальное число в множестве R, а элемент в R равен 0,1,2,3... maxXor (элемент max ( a, b) может быть не в R), используя хеш-таблицу, набор вычислений L. Но алгоритм потребляет 4 секунды, когда a = 30, b = 100000.

Приведите пример:

a = 2, b = 4, so

L = {1 * 1, 1 * 2, 1 * 3, 1 * 4, 2 * 1, 2 * 2, 2 * 3, 2 * 4} =  {1, 2, 3, 4, 6, 8}

R =  {1^1,1^2,1^3,1^4,2^1,2^2,2^3,2^4} =  {0, 1, 2, 3, 5, 6}

Все сгенерированное целое число AB:

{

100, 101, 102, 103, 105, 106,

200, 201, 202, 203, 205, 206,

300, 301, 302, 303, 305, 306,

400, 401, 402, 403, 405, 406,

600, 601, 602, 603, 605, 606,

800, 801, 802, 803, 805, 806

}

сумма всех AB равна 14502

Ответы

Ответ 1

Таким образом, число AB может быть записано как 10^(n+1) A + B. Это означает, что суммируя все A, B, сумма равна

|R| 10^(n+1) Sum(A in L) + |L| Sum(B in R)

В вашем примере

|L| = 6
|R| = 6
Sum(A in L) = 24
Sum(B in R) = 17
n = 3

который при подключении к приведенной выше формуле дает 14 502.

Это уменьшает время выполнения в размере наборов от квадратичного до линейного, поэтому вы должны увидеть довольно значительное улучшение.

Следующие биты я не полностью раскрыл, потому что у меня нет времени, но они чувствуют, что они должны работать:

  • Во-первых, обратите внимание, что Sum(A in L) будет тривиально вычисляться с использованием

    1 + 2 + .. + n = n(n-1)/2

    если не было ограничения, что L не содержит повторений. Вы можете обойти это, хотя, используя тот факт, что a очень мал: итеративно вычисляйте суммы 1, .., a с использованием формулы треугольного числа и используйте эту информацию, чтобы избежать подсчета продукта более одного раза.

  • Для Sum(B in R) обратите внимание, что при сравнении y и x^y не больше первых битов lg(a) изменились. Таким образом, вы можете разделить сумму x^y на две суммы: одну, которая имеет дело с битами от lg(a)+1 вверх и которая зависит только от b, а вторая, более сложная сумма, которая имеет дело с битами из lg(a) вниз и зависит от a и b.

Редактировать: OP попросил меня рассказать о том, как быстро вычислить Sum(A in L). В предыдущем редактировании было много вещей в этом разделе, но я действительно сел и работал через него сейчас, а не случайно, валял его в голове. Это также оказалось более сложным, чем я ожидал, поэтому я извинился за то, что не садился и не работал через него раньше @tenos.

Итак, что мы хотим сделать, это взять сумму всех различных продуктов x*y таких, что 1 <= x <= a и 1 <= y <= b. Ну, это оказалось довольно сложно, поэтому начнем с более простой проблемы: задайте два целых числа x1, x2 с x1 < x2, как мы можем вычислить сумму всех различных продуктов x1*y или x2*y, где 1 <= y <= b?

Если мы отбросим критерий четкости, это будет легко: просто будет

x1*Sum(b) + x2*Sum(b)

где Sum(j) обозначает сумму целых чисел 1 через j включительно и может быть вычислена по формуле Гаусса для треугольных чисел. Таким образом, мы снова можем свести проблему к чему-то более простому: как мы можем найти сумму всех продуктов, которые появляются как в левом, так и в правом терминах?

Ну, два продукта равны, если

x1*y1 == x2*y2

Это происходит именно тогда, когда x1*y1 == x2*y2 == k*LCM(x1, x2), где LCM является самым низким общим числом и k является некоторым целым числом.

Сумма этого для всех k такая, что 1 <= k*LCM(x1, x2) <= x1*b есть

R(x1, x2) = LCM(x1, x2) * Sum(x1*b/LCM(x1, x2))

где R означает "повторы". Это означает, что наша сумма всех различных продуктов x1*y или x2*y, где 1 <= y <= b равна

x1*Sum(b) + x2*Sum(b) - R(x1, x2)

Далее, расширим определение R на три переменные x1 < x2 < x3 как

R(x1, x2, x3) = LCM(x1, x2, x3) * Sum(x1*b/LCM(x1, x2, x3))

и аналогично для 4 переменных, 5 переменных и т.д. Тогда сумма различных произведений для трех x1 < x2 < x3 равна

x1*Sum(b) + x2*Sum(b) + x3*Sum(b) - R(x1, x2) - R(x1, x3) - R(x2, x3) + R(x1, x2, x3)

с помощью принципа исключения включения.

Итак, давайте использовать это. Определение

Sum for x = 1: 1*Sum(b)
Sum for x = 2: 2*Sum(b) - R(2, 1)
Sum for x = 3: 3*Sum(b) - R(3, 2) - R(3, 1) + R(3, 2, 1)

Etc. Тогда сумма всех этих сумм до x = a является суммой всех различных произведений.

Изменить: @tenos превратил это в полезное решение. Он заметил, что поскольку я * Sum (b) содержит много повторов, мы можем заменить на я * sum (k... b), k = max (b/minPrimeFactor (i) + 1, i).

Кроме того, при использовании принципа исключения включения многие ненужные вычисления могут быть обрезаны. Например, если R (1,2) = NULL, нет необходимости вычислять R (1,2,3), R (1,2,4)... и т.д. На самом деле, когда b очень велико, существует много R (i,.. j) = NULL.