Я вижу, что многие люди ответили на вопрос о переполнении, но я хотел решить его первоначальную проблему. Он сказал, что проблема заключается в том, чтобы найти b = c, чтобы все цифры использовались без повторения. Хорошо, это не то, что он спрашивал в этом посте, но я все еще думаю, что было необходимо изучить верхнюю границу проблемы и сделать вывод, что ему никогда не понадобится рассчитывать или обнаруживать переполнение (примечание: я не опытный в математике я сделал это шаг за шагом, но конечный результат был настолько прост, что это могло бы иметь простую формулу).
Суть в том, что верхняя граница, которая требуется для задачи a, b или c, равна 98.765.432. В любом случае, начнем с разбиения задачи на тривиальные и нетривиальные части:
- x 0 == 1 (все перестановки 9, 8, 7, 6, 5, 4, 3, 2 являются решениями)
- x 1 == x (решение невозможно)
- 0 b == 0 (решение невозможно)
- 1 b == 1 (решение невозможно)
- a b , a> 1, b> 1 (нетривиально)
Теперь нам просто нужно показать, что никакое другое решение невозможно и допустимы только перестановки (и тогда код для их печати тривиален). Возвращаемся к верхней границе. На самом деле верхняя граница составляет c ≤ 98,765,432. Это верхняя граница, потому что это наибольшее число с 8 цифрами (всего 10 цифр минус 1 для каждого a и b). Эта верхняя граница только для c, потому что границы для a и b должны быть намного ниже из-за экспоненциального роста, как мы можем вычислить, варьируя b от 2 до верхней границы:
9938.08^2 == 98765432
462.241^3 == 98765432
99.6899^4 == 98765432
39.7119^5 == 98765432
21.4998^6 == 98765432
13.8703^7 == 98765432
9.98448^8 == 98765432
7.73196^9 == 98765432
6.30174^10 == 98765432
5.33068^11 == 98765432
4.63679^12 == 98765432
4.12069^13 == 98765432
3.72429^14 == 98765432
3.41172^15 == 98765432
3.15982^16 == 98765432
2.95305^17 == 98765432
2.78064^18 == 98765432
2.63493^19 == 98765432
2.51033^20 == 98765432
2.40268^21 == 98765432
2.30883^22 == 98765432
2.22634^23 == 98765432
2.15332^24 == 98765432
2.08826^25 == 98765432
2.02995^26 == 98765432
1.97741^27 == 98765432
Обратите внимание, например, на последнюю строку: там написано, что 1.97 ^ 27 ~ 98M. Так, например, 1 ^ 27 == 1 и 2 ^ 27 == 134.217.728, и это не решение, потому что оно имеет 9 цифр (2> 1,97, поэтому оно на самом деле больше, чем должно быть проверено). Как видно, комбинации, доступные для тестирования a и b, действительно малы. Для b == 14 нам нужно попробовать 2 и 3. Для b == 3 мы начинаем с 2 и останавливаемся на 462. Все результаты предоставляются как минимум ~ 98M.
Теперь просто протестируйте все комбинации выше и найдите те, которые не повторяют никаких цифр:
['0', '2', '4', '5', '6', '7', '8'] 84^2 = 7056
['1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481
['0', '1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481 (+leading zero)
['1', '2', '3', '5', '8'] 8^3 = 512
['0', '1', '2', '3', '5', '8'] 8^3 = 512 (+leading zero)
['1', '2', '4', '6'] 4^2 = 16
['0', '1', '2', '4', '6'] 4^2 = 16 (+leading zero)
['1', '2', '4', '6'] 2^4 = 16
['0', '1', '2', '4', '6'] 2^4 = 16 (+leading zero)
['1', '2', '8', '9'] 9^2 = 81
['0', '1', '2', '8', '9'] 9^2 = 81 (+leading zero)
['1', '3', '4', '8'] 3^4 = 81
['0', '1', '3', '4', '8'] 3^4 = 81 (+leading zero)
['2', '3', '6', '7', '9'] 3^6 = 729
['0', '2', '3', '6', '7', '9'] 3^6 = 729 (+leading zero)
['2', '3', '8'] 2^3 = 8
['0', '2', '3', '8'] 2^3 = 8 (+leading zero)
['2', '3', '9'] 3^2 = 9
['0', '2', '3', '9'] 3^2 = 9 (+leading zero)
['2', '4', '6', '8'] 8^2 = 64
['0', '2', '4', '6', '8'] 8^2 = 64 (+leading zero)
['2', '4', '7', '9'] 7^2 = 49
['0', '2', '4', '7', '9'] 7^2 = 49 (+leading zero)
Ни один из них не соответствует проблеме (что также можно увидеть по отсутствию '0', '1', ..., '9').
Пример кода, который решает его, следует. Также обратите внимание, что он написан на python, не потому, что ему нужны целые числа произвольной точности (код не вычисляет ничего больше, чем 98 миллионов), а потому, что мы обнаружили, что количество тестов настолько мало, что мы должны использовать язык высокого уровня используйте встроенные контейнеры и библиотеки (также обратите внимание: в коде 28 строк).
import math
m = 98765432
l = []
for i in xrange(2, 98765432):
inv = 1.0/i
r = m**inv
if (r < 2.0): break
top = int(math.floor(r))
assert(top <= m)
for j in xrange(2, top+1):
s = str(i) + str(j) + str(j**i)
l.append((sorted(s), i, j, j**i))
assert(j**i <= m)
l.sort()
for s, i, j, ji in l:
assert(ji <= m)
ss = sorted(set(s))
if s == ss:
print '%s %d^%d = %d' % (s, i, j, ji)
# Try with non significant zero somewhere
s = ['0'] + s
ss = sorted(set(s))
if s == ss:
print '%s %d^%d = %d (+leading zero)' % (s, i, j, ji)