Задача №1389. Верное равенство
Возвращаясь из школы домой, Петя каждый раз обращал внимание на надпись на заборе «1 + 1 = 10» и удивлялся очевидной его неправоте. Но однажды его осенило, что это равенство верное, если рассматривать его в двоичной системе счисления. Его настолько поразила эта идея, что он решил непременно придумать свои три числа так, чтобы сумма первых двух была равна третьему в некоторой системе счисления.
Теперь он перебирает тройки чисел, которые, на его взгляд, достойны находиться на заборе. Петя выбирает числа A, B, C, записывающиеся десятичными цифрами, и дальше пытается найти основание системы счисления K, в которой равенство A + B = C оказалось бы верным. Петя рассматривает системы счисления с основанием от 2 до бесконечности.
Поскольку проверка каждой тройки — занятие трудоемкое, в помощь Пете необходимо написать программу, облегчающую расчеты.
В первой строке содержится число A, состоящее из цифр от 0 до 9 длины не более 200. В следующих двух строках в таком же формате записаны числа B и C.
Все числа неотрицательные и без ведущих нулей.
Выведите минимальное основание системы счисления, в которой выполняется равенство A + B = C. Если такого не существует, то выведите 0.
Частичные ограничения
Первая группа состоит из тестов, в которых у всех трех чисел количество цифр не превышает 5, а при сложении их «столбиком» в искомой системе счисления не происходит переноса в следующий разряд.
Вторая группа состоит из чисел, при переводе которых из искомой системы счисления в десятичную они не будут превышать 109.
9 8 17
10
9 8 11
16
5 5 1010
0
0 0 0
2