1. Идея

Нужно закодировать строку в стандартный Base64.

Base64 работает так:

• берём исходные байты по 3 штуки;
• объединяем их в один 24-битный блок;
• разбиваем этот блок на 4 части по 6 бит;
• каждую 6-битную часть заменяем символом из специального алфавита: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

Если в конце строки осталось меньше 3 символов, недостающие байты считаются нулями, а в ответ добавляются символы =.

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

2.1. Почему именно по 3 символа

Один ASCII-символ занимает 1 байт, то есть 8 бит.

Три символа — это 3 * 8 = 24 бита.

Base64 кодирует данные группами по 6 бит, а 24 = 4 * 6, поэтому из каждых 3 байт получается ровно 4 символа Base64.

2.2. Алфавит Base64

Индексы от 0 до 63 соответствуют символам:

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

То есть если очередная 6-битная группа равна, например, 0, то берётся A, если 1 — B, и так далее.

2.3. Что делать, если символов осталось 1 или 2

• Если остался 1 байт:

  • формируем 24-битный блок из этого байта и двух нулевых байтов;
  • первые 2 символа Base64 настоящие;
  • последние 2 заменяются на ==.

• Если осталось 2 байта:

  • формируем 24-битный блок из двух байтов и одного нулевого;
  • первые 3 символа Base64 настоящие;
  • последний заменяется на =.

Именно так и устроено стандартное Base64-дополнение.

3. Алгоритм

Пусть дана строка s.

1. Создаём строку алфавита Base64.
2. Идём по строке с шагом 3.
3. Для каждой позиции:
   • берём первый байт b1;
   • если есть второй символ, берём b2, иначе 0;
   • если есть третий символ, берём b3, иначе 0.
4. Собираем число из 24 бит:
   • x = (b1 << 16) | (b2 << 8) | b3
5. Извлекаем 4 группы по 6 бит:
   • (x >> 18) & 63
   • (x >> 12) & 63
   • (x >> 6) & 63
   • x & 63
6. По этим индексам берём символы из алфавита.
7. Если реальных байтов было меньше 3, заменяем последние символы на = по правилам:
   • если был только 1 байт, дописываем ==;
   • если было 2 байта, дописываем =.
8. Выводим результат.

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

Рассмотрим очередные 3 байта: b1, b2, b3.

Мы строим число:

x = (b1 << 16) | (b2 << 8) | b3

Это означает, что:

• b1 занимает старшие 8 бит,
• b2 — средние 8 бит,
• b3 — младшие 8 бит.

Получается ровно 24 бита исходных данных.

Теперь делим их на 4 группы по 6 бит:

• старшие 6 бит: (x >> 18) & 63
• следующие 6 бит: (x >> 12) & 63
• следующие 6 бит: (x >> 6) & 63
• последние 6 бит: x & 63

Каждое такое число лежит в диапазоне от 0 до 63, поэтому его можно использовать как индекс в Base64-алфавите.

Если в конце не хватает байтов, мы подставляем нули. Это позволяет корректно получить нужные старшие группы бит, соответствующие стандарту Base64. Лишние символы результата помечаются =, чтобы было видно, что исходных байтов было меньше 3.

Значит, алгоритм в точности реализует стандартное Base64-кодирование.

5. Сложность

Пусть длина строки равна n.

• Время работы: O(n), потому что каждый символ обрабатывается один раз.
• Дополнительная память: O(n), так как нужно хранить результирующую строку.

6. Код на C++17

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    getline(cin, s);

    const string base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    string ans;

    int n = (int)s.size();
    for (int i = 0; i < n; i += 3) {
        int rem = n - i;

        int b1 = (unsigned char)s[i];
        int b2 = 0;
        int b3 = 0;

        if (rem > 1) b2 = (unsigned char)s[i + 1];
        if (rem > 2) b3 = (unsigned char)s[i + 2];

        int x = (b1 << 16) | (b2 << 8) | b3;

        ans += base64[(x >> 18) & 63];
        ans += base64[(x >> 12) & 63];

        if (rem > 1) {
            ans += base64[(x >> 6) & 63];
        } else {
            ans += '=';
        }

        if (rem > 2) {
            ans += base64[x & 63];
        } else {
            ans += '=';
        }
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

s = input()

base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
ans = []

n = len(s)
for i in range(0, n, 3):
    rem = n - i

    b1 = ord(s[i])
    b2 = ord(s[i + 1]) if rem > 1 else 0
    b3 = ord(s[i + 2]) if rem > 2 else 0

    x = (b1 << 16) | (b2 << 8) | b3

    ans.append(base64[(x >> 18) & 63])
    ans.append(base64[(x >> 12) & 63])

    if rem > 1:
        ans.append(base64[(x >> 6) & 63])
    else:
        ans.append('=')

    if rem > 2:
        ans.append(base64[x & 63])
    else:
        ans.append('=')

print("".join(ans))