Задание 14

В этом задании нужно сложить большие числа и сказать, сколько в них тех или иных цифр

Пример 1

Задача

Значение арифметического выражения: $49^7 + 7^{21} – 7$ – записали в системе счисления с основанием $7$. Сколько цифр $6$ содержится в этой записи?

Java

import java.math.BigInteger;

public class Example2 {
    public static void main(String[] args) {
        // первое значение
        BigInteger value1 = BigInteger.valueOf(49).pow(7);
        // второе значение
        BigInteger value2 = BigInteger.valueOf(7).pow(21);
        // третье
        BigInteger value3 = BigInteger.valueOf(7);
        // вычисляем результат
        BigInteger result = value1.add(value2).subtract(value3);
        // формируем строку представляющее число в семеричной системе счисления
        String resultString = result.toString(7);
        // кол-во нужных цифр 0
        int cnt = 0;
        // перебираем все цифры
        for (char c : resultString.toCharArray()) {
            // если цифра равна 6
            if (c == '6')
                // увеличиваем кол-во на 1
                cnt++;
        }
        // выводим кол-во символов
        System.out.println(cnt);
    }
}

C++

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

// основание системы счисления
const int BASE = 7;

// после операций сложения и вычетания в начале вектора может появиться несколько
// нулей, этот метод удаляет их
std::vector<int> removeBeginZeros(std::vector<int> v) {
    while (v[0] == 0) {
        v.erase(v.begin());
    }
    return v;
}

// сумма длинных чисел
std::vector<int> plus(std::vector<int> a, std::vector<int> b) {
    // ответ
    std::vector<int> res;
    // выделяем сразу память под результат
    res.reserve(std::max(a.size(), b.size()));
    // если первый вектор длиннее второго
    if (a.size() > b.size())
        // добавляем в начале второго вектора нули
        for (int i = 0; a.size() - b.size(); i++)
            b.insert(b.begin(), 0);
    else
        // добавляем в начале первого вектора нули
        for (int i = 0; b.size() - a.size(); i++)
            a.insert(a.begin(), 0);
    // перенос
    int add = 0;
    // перебираем разряды чисел
    for (int i = 0; i < a.size(); i++) {
        // разряды числа идут в обратном порядке
        int sum = a[a.size() - 1 - i] + b[b.size() - 1 - i] + add;
        // если поразрядная сумма больше основания
        if (sum >= BASE) {
            // вычитаем основание из суммы
            sum -= BASE;
            // перенос равен 1
            add = 1;
        } else
            // переноса нет
            add = 0;
        // добавляем сумму в вектор
        res.push_back(sum);
    }
    // если после суммы перенос больше нуля
    if (add > 0)
        // добавляем его в вектор
        res.push_back(add);
    // сформированный вектор создан развёрнутым,
    // чтобы разряды шли в том же порядке, что и в числе,
    // необходимо развернуть вектор
    std::reverse(res.begin(), res.end());
    // убираем нули в начале вектора-результата
    return removeBeginZeros(res);
}

// вычетание длинных чисел(предполагается, что первый вектор больше второго,
// т.е. результат всегда положительный
std::vector<int> minus(std::vector<int> a, std::vector<int> b) {
    // ответ
    std::vector<int> res;
    // выделяем сразу память под результат
    res.reserve(std::max(a.size(), b.size()));
    // если первый вектор длиннее второго
    if (a.size() > b.size())
        // добавляем в начале второго вектора нули
        for (int i = 0; a.size() - b.size(); i++)
            b.insert(b.begin(), 0);
    else
        // добавляем в начале первого вектора нули
        for (int i = 0; b.size() - a.size(); i++)
            a.insert(a.begin(), 0);
    // перенос
    int add = 0;
    // перебираем разряды чисел
    for (int i = 0; i < a.size(); i++) {
        // разряды числа идут в обратном порядке
        int sub = a[a.size() - 1 - i] - b[b.size() - 1 - i] + add;
        // если поразрядная разность меньше нуля
        if (sub < 0) {
            // к разности добавляем основание
            sub += BASE;
            // перенос равен -1
            add = -1;
        } else
            // переноса нет
            add = 0;
        // добавляем разность в вектор
        res.push_back(sub);
    }
    // сформированный вектор создан развёрнутым,
    // чтобы разряды шли в том же порядке, что и в числе,
    // необходимо развернуть вектор
    std::reverse(res.begin(), res.end());
    // убираем нули в начале вектора-результата
    return removeBeginZeros(res);
}

// получение числа, равного овнованию в заданной степени
std::vector<int> pow(int p) {
    std::vector<int> vec;
    // изначально число равно 1
    vec.push_back(1);
    // домножаме его на основание p раз, добавляя ноль в конец dtrnjhf
    for (int i = 0; i < p; i++) {
        vec.push_back(0);
    }
    return vec;
}

// перевод произвольного числа в длинное с заданным основанием
std::vector<int> valueOf(int a) {
    // результат
    std::vector<int> res;
    // пока в числе есть цифры в семеричном представлении
    while (a > 0) {
        // добавляем в вектор последнюю цифру в семеричном представлении
        res.push_back(a % BASE);
        // отбрасываем её
        a /= BASE;
    }
    // разворачиваем вектор-результат
    std::reverse(res.begin(), res.end());
    return res;
}


int main() {
    // первое большое число
    std::vector<int> a = pow(7 * 2);
    // второе большое число
    std::vector<int> b = pow(21);
    // третье большое число
    std::vector<int> c = valueOf(7);

    // вычисляем результат
    std::vector<int> r = minus(plus(a, b), c);

    // кол-во шестёрок изначально равно нулю
    int count6 = 0;
    // перебираем цифры числа
    for (int i: r) {
        // если цифра равна 6
        if (i == 6)
            // увеличиваем кол-во на 1
            count6++;
    }
    // выводим кол-во шестёрок
    std::cout << count6 << std::endl;
    return 0;
}

Python

# задаём значение
x = 49 ** 7 + 7 ** 21 - 7
# кол-во шетёрок равно 0
count6 = 0
# пока число больше 0
while x:
    # если остаток от деления на 7 равен 0
    if x % 7 == 6:
        # увеличивае кол-во
        count6 += 1
    # делим число на 7
    x //= 7
# выводим ответ
print(count6)

Программы выведет:

13

Ответ: 13.

В Java есть готовый инструмент для работы с ддлинной арифметикой. Для этого вам понадобится класс BigInteger. Чтобы создать длинное число, необходимо вызвать команду:

    BigInteger value1 = BigInteger.valueOf(49);

Команды можно вызывать подряд, например, чтобы получить число $49^7$, необходимо вызвать подряд две команды

    BigInteger value1 = BigInteger.valueOf(49).pow(7);

первая valueOf() создаёт длинное число, вторая pow() - возводит созданное прошлой командой число в заданную степень.

Вычетание subtract() и сложение add() тоже можно вызывать цепочкой.

    BigInteger result = value1.add(value2).subtract(value3);

Обратите внимание: add() и subtract() в качестве аргументов принимают только объекты BigInteger.

В C++ нет готового инструмента для работы с длинной арифметикой, поэтому придётся писать её самостоятельно. Правда, в задании только сложение, вычетание и возведение основания в степень. Поэтому можно просто написать эти три метода.

Обычно длинная арифметика реализуется на строках, но в нашем случае проще использовать целочисленный вектор. Да, такое решение сильно неоптимальное, но на ЕГЭ надо просто решить задачу, поэтому чем проще написать работающую программу, тем лучше.

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

Пример 2

Задача

Сколько значащих нулей в двоичной записи числа

$4^{512} + 8^{512} – 2^{128} – 250$

Java

import java.math.BigInteger;

public class Example2 {
    public static void main(String[] args) {
        // первое значение
        BigInteger value1 = BigInteger.valueOf(4).pow(512);
        // второе значение
        BigInteger value2 = BigInteger.valueOf(8).pow(512);
        // третье
        BigInteger value3 = BigInteger.valueOf(2).pow(128);
        // четвёртое
        BigInteger value4 = BigInteger.valueOf(250);

        // вычисляем результат
        BigInteger result = value1.add(value2).subtract(value3).subtract(value4);

        // формируем строку представляющее число в двоичной системе счисления
        String resultString = result.toString(2);
        // кол-во нужных цифр 0
        int cnt = 0;
        // перебираем все цифры
        for (char c : resultString.toCharArray()) {
            // если цифра равна 6
            if (c == '0')
                // увеличиваем кол-во на 1
                cnt++;
        }
        // выводим кол-во символов
        System.out.println(cnt);
    }
}

C++

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

// основание системы счисления
const int BASE = 2;

// после операций сложения и вычетания в начале вектора может появиться несколько
// нулей, этот метод удаляет их
std::vector<int> removeBeginZeros(std::vector<int> v) {
    while (v[0] == 0) {
        v.erase(v.begin());
    }
    return v;
}

// сумма длинных чисел
std::vector<int> plus(std::vector<int> a, std::vector<int> b) {
    // ответ
    std::vector<int> res;
    // выделяем сразу память под результат
    res.reserve(std::max(a.size(), b.size()));
    // если первый вектор длиннее второго
    if (a.size() > b.size())
        // добавляем в начале второго вектора нули
        for (int i = 0; a.size() - b.size(); i++)
            b.insert(b.begin(), 0);
    else
        // добавляем в начале первого вектора нули
        for (int i = 0; b.size() - a.size(); i++)
            a.insert(a.begin(), 0);
    // перенос
    int add = 0;
    // перебираем разряды чисел
    for (int i = 0; i < a.size(); i++) {
        // разряды числа идут в обратном порядке
        int sum = a[a.size() - 1 - i] + b[b.size() - 1 - i] + add;
        // если поразрядная сумма больше основания
        if (sum >= BASE) {
            // вычитаем основание из суммы
            sum -= BASE;
            // перенос равен 1
            add = 1;
        } else
            // переноса нет
            add = 0;
        // добавляем сумму в вектор
        res.push_back(sum);
    }
    // если после суммы перенос больше нуля
    if (add > 0)
        // добавляем его в вектор
        res.push_back(add);
    // сформированный вектор создан развёрнутым,
    // чтобы разряды шли в том же порядке, что и в числе,
    // необходимо развернуть вектор
    std::reverse(res.begin(), res.end());
    // убираем нули в начале вектора-результата
    return removeBeginZeros(res);
}

// вычетание длинных чисел(предполагается, что первый вектор больше второго,
// т.е. результат всегда положительный
std::vector<int> minus(std::vector<int> a, std::vector<int> b) {
    // ответ
    std::vector<int> res;
    // выделяем сразу память под результат
    res.reserve(std::max(a.size(), b.size()));
    // если первый вектор длиннее второго
    if (a.size() > b.size())
        // добавляем в начале второго вектора нули
        for (int i = 0; a.size() - b.size(); i++)
            b.insert(b.begin(), 0);
    else
        // добавляем в начале первого вектора нули
        for (int i = 0; b.size() - a.size(); i++)
            a.insert(a.begin(), 0);
    // перенос
    int add = 0;
    // перебираем разряды чисел
    for (int i = 0; i < a.size(); i++) {
        // разряды числа идут в обратном порядке
        int sub = a[a.size() - 1 - i] - b[b.size() - 1 - i] + add;
        // если поразрядная разность меньше нуля
        if (sub < 0) {
            // к разности добавляем основание
            sub += BASE;
            // перенос равен -1
            add = -1;
        } else
            // переноса нет
            add = 0;
        // добавляем разность в вектор
        res.push_back(sub);
    }
    // сформированный вектор создан развёрнутым,
    // чтобы разряды шли в том же порядке, что и в числе,
    // необходимо развернуть вектор
    std::reverse(res.begin(), res.end());
    // убираем нули в начале вектора-результата
    return removeBeginZeros(res);
}

// получение числа, равного овнованию в заданной степени
std::vector<int> pow(int p) {
    std::vector<int> vec;
    // изначально число равно 1
    vec.push_back(1);
    // домножаме его на основание p раз, добавляя ноль в конец dtrnjhf
    for (int i = 0; i < p; i++) {
        vec.push_back(0);
    }
    return vec;
}

// перевод произвольного числа в длинное с заданным основанием
std::vector<int> valueOf(int a) {
    // результат
    std::vector<int> res;
    // пока в числе есть цифры в семеричном представлении
    while (a > 0) {
        // добавляем в вектор последнюю цифру в семеричном представлении
        res.push_back(a % BASE);
        // отбрасываем её
        a /= BASE;
    }
    // разворачиваем вектор-результат
    std::reverse(res.begin(), res.end());
    return res;
}

int main() {
    // первое большое число
    std::vector<int> a = pow(512 * 2);
    // второе большое число
    std::vector<int> b = pow(512 * 3);
    // третье большое число
    std::vector<int> c = pow(128);
    // четвёртое большое число
    std::vector<int> d = valueOf(250);
    // результат
    std::vector<int> r = minus(minus(plus(a, b), c), d);

    // кол-во нулей изначально равно нулю
    int count0 = 0;
    // перебираем цифры числа
    for (int i: r) {
        // если цифра равна 0
        if (i == 0)
            // увеличиваем кол-во на 1
            count0++;
    }
    // выводим кол-во
    std::cout << count0 << std::endl;
    return 0;
}

Python

# задаём значение
x = 4 ** 512 + 8 ** 512 - 2 ** 128 - 250
# кол-во шетёрок равно 0
count0 = 0
# пока число больше 0
while x:
    # если остаток от деления на 7 равен 0
    if x % 2 == 0:
        # увеличивае кол-во
        count0 += 1
    # делим число на 7
    x //= 2
# выводим ответ
print(count0)

Программа выведет:

519

Пример 3

Задача

Решите уравнение

$$60_8+x=120_7$$

Ответ запишите в шестеричной системе счисления. Основание системы счисления указывать не нужно.

удобнее всего перевести все числа в десятичную систему, решить уравнение и результат перевести в шестеричную систему

получаем

$$60_8=6*8^1+0*8^0=48,~ 120_7=1*7^2+2*7^1=63$$

уравнение приобретает вид

$$48+x=63$$

откуда получаем

$$x =15$$

переводим 15 в шестеричную систему счисления:

$$15=2*6^1+3*6^0=23_6$$

Ответ: 23_6

Пример 4

Задача

Запись числа $381_{10}$ в системе счисления с основанием N оканчивается на 3 и содержит 3 цифры. Укажите наибольшее возможное основание этой системы счисления N.

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

Java

public class Example3 {
    public static void main(String[] args) {
        // исходное число
        int val = 381;
        // перебираем основания
        for (int i = 32; i >= 0; i--) {
            // создаём строку с представлением перебираемого значения
            //  в системе счиления с основанием i
            String s = Integer.toString(val, i);
            // если число оканчивается на тройку и содержит три цифры
            if (s.charAt(s.length()-1)=='3'&&s.length()==3){
                // выводим основание
                System.out.println(i);
                // останавливаем цикл
                break;
            }
        }
    }
}

C++

#include <iostream>
#include <set>

// главный метод программы
int main() {
    // исходное число
    int val = 381;
    // перебираем основания
    for (int i = 32; i >= 0; i--) {
        // создаём строку с двоичным представлением перебираемого значения
        char p[17];
        // отправляем в буфер p строковое представление числа с заданным основанием
        itoa(val, p, i);
        // создаём строку на основе буффера
        std::string s(p);
        if (s[s.length()-1]=='3'&&s.length()==3){
            // выводим основание
            std::cout<<i<<std::endl;
            // останавливаем цикл
            break;
        }
    }
}

Python

# исходное число
val = 381
# перебираем основания
for n in range(32, 1, -1):
    # создаём список цифр
    d = list()
    i = val
    while i > 0:
        d.append(i % n)
        # отбрасываем младший разряд числа
        i = i // n

    # в массиве цифры расположены по разрядам,
    # поэтому элементы для сумм берутся в обратном порядке
    if d[0] == 3 and len(d) == 3:
        print(n)
        break

Программа выведет:

18

Ответ: 18

Задания для самостоятельного выполнения