1. Идея

Нужно сложить n чисел, где каждое записано в своей системе счисления, а затем вывести сумму в системе с основанием target_base.

Главная сложность в том, что длина каждой записи может быть до 100, а чисел до 10^4, поэтому сумма может получиться очень большой. Обычные типы вроде int или long long тут не подходят.

Поэтому используется длинная арифметика:

• храним текущее значение суммы как большое число;
• для чтения очередной записи переводим её в значение поразрядно;
• но не отдельно в новое число, а сразу накапливаем в общей сумме;
• в конце переводим большое число в целевую систему счисления.

В эталонном решении большое число хранится как массив блоков по основанию 10^9.

2. Наблюдения

Наблюдение 1. Как перевести строку из системы счисления в число

Если число записано строкой value в системе с основанием base, то его можно обработать слева направо.

Пусть уже прочитанная часть равна x. Тогда после добавления следующей цифры d новое значение будет:

x = x * base + d

Например, для строки 1a в системе 16:

• сначала x = 0
• читаем 1: x = 0 * 16 + 1 = 1
• читаем a: x = 1 * 16 + 10 = 26

Именно это и делает решение.

Наблюдение 2. Можно не хранить каждое число отдельно

В условии нужно найти сумму всех чисел. Значит, можно обрабатывать каждую запись по очереди и сразу прибавлять её вклад к общей сумме.

Эталонное решение делает это очень компактно: для каждой цифры каждой строки обновляется одно общее большое число sum.

Наблюдение 3. Для перевода из большого числа в нужную систему удобно делить

Чтобы получить запись числа в системе с основанием target_base, удобно многократно делить число на target_base:

• остаток от деления — это последняя цифра;
• затем заменяем число на частное и повторяем.

Так можно получить цифры ответа с конца, а потом развернуть строку.

Наблюдение 4. Основания маленькие

Все системы счисления имеют основания от 2 до 36. Это очень удобно:

• умножение большого числа на base — это умножение на маленькое число;
• прибавление очередной цифры — тоже прибавление маленького числа;
• деление на target_base — деление на маленькое число.

Поэтому не нужна сложная длинная арифметика: достаточно операций над большим числом и маленьким числом.

3. Алгоритм

Будем хранить большое число как массив a блоков по основанию 10^9 в порядке от младших к старшим.

Например, число хранится так:

• a[0] — младший блок
• a[1] — следующий
• и так далее

Операции над большим числом

Нужны три операции:

1. mul_small(m) — умножить большое число на маленькое число m
2. add_small(v) — прибавить маленькое число v
3. div_small(d) — разделить большое число на маленькое число d, вернуть остаток

Также полезны:

• trim() — удалить ведущие нулевые блоки
• isZero() — проверить, равно ли число нулю

Построение суммы

Пусть sum — текущее большое число.

Для каждой строки base value:

• для каждого символа c из value:
  • переводим символ в цифру d
  • делаем sum = sum * base + d

После обработки всех строк в sum находится сумма всех записей, интерпретированных как числа.

Перевод суммы в target_base

Если sum = 0, выводим 0.

Иначе:

• пока sum не равно нулю:
  • rem = sum.div_small(target_base)
  • добавляем символ цифры rem в конец строки результата
• переворачиваем строку
• выводим её

4. Почему это работает

Докажем корректность по шагам.

Шаг 1. Корректный перевод одной записи

Рассмотрим строку value = c1 c2 ... ck в системе счисления с основанием base.

Пусть после обработки первых i символов текущее значение равно числу, записанному префиксом c1 ... ci.

Изначально до обработки символов значение равно 0, что верно.

Если следующий символ имеет значение d, то новое число должно быть равно:

старое_значение * base + d

Это стандартное правило для позиционной записи числа. Значит, после обработки всех символов получаем именно числовое значение всей строки.

Шаг 2. Корректность накопления суммы

В решении одна общая переменная sum обновляется по всем строкам подряд. После обработки первой строки в sum лежит значение этой строки. После обработки второй строки в sum получается:

предыдущее * base + digit ...

То есть для каждой новой строки её цифры по описанному правилу добавляют в сумму ровно значение этой строки. В результате после обработки всех n строк в sum находится сумма всех чисел.

Шаг 3. Корректность перевода в целевую систему

Известно свойство позиционной записи: если число x делить на основание b, то остаток — это последняя цифра записи числа в системе b, а частное — это число без последней цифры.

Поэтому, если многократно:

• брать остаток от деления на target_base,
• заменять число на частное,

то мы последовательно получим цифры записи справа налево. После разворота получится правильная запись числа в целевой системе счисления.

Шаг 4. Корректность операций длинной арифметики

Большое число хранится как сумма блоков по основанию 10^9. Операции:

• умножение на маленькое число,
• прибавление маленького числа,
• деление на маленькое число

выполняются обычным школьным способом с переносами и остатками по блокам. Значит, каждая операция сохраняет точное значение числа.

Следовательно, весь алгоритм работает корректно.

5. Сложность

Пусть:

• L — суммарная длина всех входных строк,
• K — число блоков большого числа в основании 10^9

Тогда:

• каждая операция mul_small, add_small, div_small работает за O(K)
• чтение всех цифр требует O(L) шагов длинной арифметики
• перевод результата в целевую систему требует ещё несколько делений, каждое за O(K)

Итогово асимптотика получается порядка O(количество_операций_над_цифрами * K).

Для данных ограничений этого достаточно.

По памяти хранится только одно большое число, то есть O(K).

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

struct BigInteger {
    static const int BASE = 1000000000;
    vector<int> a; // little-endian blocks

    void trim() {
        while (!a.empty() && a.back() == 0) a.pop_back();
    }

    bool isZero() const {
        return a.empty();
    }

    void mul_small(int m) {
        if (isZero() || m == 1) return;
        if (m == 0) {
            a.clear();
            return;
        }
        long long carry = 0;
        for (int i = 0; i < (int)a.size(); i++) {
            long long cur = 1LL * a[i] * m + carry;
            a[i] = (int)(cur % BASE);
            carry = cur / BASE;
        }
        while (carry > 0) {
            a.push_back((int)(carry % BASE));
            carry /= BASE;
        }
    }

    void add_small(int v) {
        long long carry = v;
        int i = 0;
        while (carry > 0) {
            if (i == (int)a.size()) a.push_back(0);
            long long cur = 1LL * a[i] + carry;
            a[i] = (int)(cur % BASE);
            carry = cur / BASE;
            i++;
        }
    }

    int div_small(int d) {
        long long rem = 0;
        for (int i = (int)a.size() - 1; i >= 0; i--) {
            long long cur = a[i] + rem * BASE;
            a[i] = (int)(cur / d);
            rem = cur % d;
        }
        trim();
        return (int)rem;
    }
};

int char_value(char c) {
    if ('0' <= c && c <= '9') return c - '0';
    return c - 'a' + 10;
}

char digit_char(int x) {
    if (x < 10) return char('0' + x);
    return char('a' + (x - 10));
}

int main() {
    int n, target_base;
    cin >> n >> target_base;

    BigInteger sum;

    for (int i = 0; i < n; i++) {
        int base;
        string value;
        cin >> base >> value;
        for (char c : value) {
            int d = char_value(c);
            sum.mul_small(base);
            sum.add_small(d);
        }
    }

    if (sum.isZero()) {
        cout << "0\n";
        return 0;
    }

    string result;
    while (!sum.isZero()) {
        int rem = sum.div_small(target_base);
        result.push_back(digit_char(rem));
    }
    reverse(result.begin(), result.end());

    cout << result << "\n";
    return 0;
}

7. Код на Python 3

BASE = 10**9

first = input().split()
n = int(first[0])
target_base = int(first[1])

a = []  # little-endian blocks in base 1e9

def trim():
    while a and a[-1] == 0:
        a.pop()

def is_zero():
    return len(a) == 0

def mul_small(m):
    global a
    if not a or m == 1:
        return
    if m == 0:
        a = []
        return
    carry = 0
    for i in range(len(a)):
        cur = a[i] * m + carry
        a[i] = cur % BASE
        carry = cur // BASE
    while carry > 0:
        a.append(carry % BASE)
        carry //= BASE

def add_small(v):
    carry = v
    i = 0
    while carry > 0:
        if i == len(a):
            a.append(0)
        cur = a[i] + carry
        a[i] = cur % BASE
        carry = cur // BASE
        i += 1

def div_small(d):
    rem = 0
    for i in range(len(a) - 1, -1, -1):
        cur = rem * BASE + a[i]
        a[i] = cur // d
        rem = cur % d
    trim()
    return rem

def char_value(c):
    if '0' <= c <= '9':
        return ord(c) - ord('0')
    return ord(c) - ord('a') + 10

def digit_char(x):
    if x < 10:
        return chr(ord('0') + x)
    return chr(ord('a') + x - 10)

for _ in range(n):
    parts = input().split()
    base = int(parts[0])
    value = parts[1]
    for c in value:
        d = char_value(c)
        mul_small(base)
        add_small(d)

if is_zero():
    print("0")
else:
    res = []
    while not is_zero():
        rem = div_small(target_base)
        res.append(digit_char(rem))
    print(''.join(reversed(res)))