Оптимизация вычисленией в коде Python

Question

Я делаю задание из ЕГЭ по информатике, оно на фото:

Мой код:

f = 18*7**108-5*49**76+343**35-50
s=0
while f!=0:
    s+=f%49
    f//=49
print(s)

выполняется очень долго, и я не получаю ответ. Как мне его ускорить, ведь школьные компьютеры в 1000 раз менее производительны?

Answer 1

7¹⁰⁸ - это 54 нуля.
49⁷⁶ - это 76 нулей.
343=7*49, поэтому 343³⁵ - это 7 и 52 нуля.

tio.run

a = [18] + [0]*54
b = [-5] + [0]*76
c = [7] + [0]*52
d = [-1, -1]
z = [0] * max(len(a), len(b), len(c), len(d))

res = [a+b+c+d for a,b,c,d,z in zip(a[::-1]+z, b[::-1]+z, c[::-1]+z, d[::-1]+z, z)]
neg = res[-1] < 0

if neg:
  res = [-x for x in res]

carry = 0
res += [49]
for i in range(len(res)):
  while res[i] < 0:
    res[i+1] -= 1
    res[i] += 49

res[-1] -= 49
if res[-1] == 0: res.pop()
else: raise Exception("overflow")

res = res[::-1]

print(sum(res))
print('-' if neg else "+", res)

1134
- [4, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 30, 48, 42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]

Answer 2

Qwertiy уже начал заводить вопрос за корягу, пока я обдумывал.

С учётом того, что 7^108=7^(2*54)=(7^2)^54=49^54 и 343^35=(7^3)^35=7^105=7*7^104=7*49^52, поменяем знак и получим 5*49^76+49+1 - (18*49^54+7*49^52). Соответственно, два числа с цифрами 5, 1 и 1 в одном и 18 и 7 в другом.

Создадим массивы для каждого числа по 77 элементов и заполним цифрами. Потом сделаем порязрядное вычитание и просуммируем результирующий массив.

Упрощая, можно использовать один массив, в который записаны коэффициенты многочлена как цифры числа с учётом знака [1, 1] + [0]*50 + [-7] + [0] + [-18] + [0]*21 + [5] в обратном порядке, так как операция выполняется от младших разрядов к старшим.

Получится простая программа:

from functools import reduce

print(reduce(lambda a, b: (a[0] + b - a[1] + (49 if b < a[1] else 0), 1 if b < a[1] else 0), [1, 1] + [0]*50 + [-7] + [0] + [-18] + [0]*21 + [5], (0, 0))[0])

1134

Первый элемент в кортеже - накапливаемая сумма, второй - признак переполнения.

Answer 3

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

f = abs(f)

Получится так: tio.run

f = 18*7**108 - 5*49**76 + 343**35 - 50
f = abs(f)

s = 0
while f:
    s += f % 49
    f //= 49

print(s)

БЛОГ НА HUSL

Оптимизация вычисленией в коде Python

Ответы (3 шт):