Задача из муниципального этапа по программированию
Задача имеет в себе 10 тестов. С числами до миллиона компьютер справляется, потом — всё.
Задача
Дано некое целое положительное число N. Нужно найти сумму чисел от 1 до N, но все числа должны дважды переворачиваться и незначащие нули должны быть удалены.
То есть есть число — 2300, сначала переворачиваем, получаем — 0032, убираем нули, получаем 32, и опять же переворачиваем, получаем 23. Но, повторюсь, каждое число от 1 до N должно быть так перевернуто. Также у полученной суммы надо найти остаток от деления на 10**9 + 7
Если предоставите решение для больших чисел, буду благодарен.
Помню несколько тестов, на которые вы можете ориентироваться:
| N | ответ |
|---|---|
| 8 | 36 |
| 19 | 181 |
| 234 | 24984 |
Скрипт:
def flip(n):
while n % 10 == 0:
n //= 10
return n
n = int(input())
sum = 0
for x in range(1, n+1):
sum += flip(x)
print(sum % (10**9 + 7))
Ответы (1 шт):
Если диапазон большой, то перебор всех чисел, конечно, не вариант.
Однако в школе нас учили вычитать и умножать, малышей не обижать... находить сумму арифметической прогрессии по простой формуле.
Для ряда 1..n эта сумма будет равна n*(n+1)/2.
Так мы получаем сумму всех чисел диапазона, но эта сумма включает и числа с терминальными нулями. Поэтому результат нужно уменьшить на сумму чисел, оканчивающихся нулём, и прибавить сумму чисел этой же выборки, делённых на 10. То же самое (с учётом десятичного порядка) с числами, оканчивающимися на два нуля, на три нуля, и так далее.
Получается, что за логарифм числа (длина его десятичной записи), т.е. практически мгновенно, мы рассчитаем всё, что нужно:
def sz(n):
res = n * (n + 1) // 2
while n:
n = n // 10
res -= 9 * n * (n+1) // 2
return res % 1000000007
Cравнение с функцией автора:
print(flipfunc(39457298), sz(39457298))
>>>11370029 11370029
Длиииннный диапазон:
print(sz(7023530680698209829384502876017846507860760876304750347503489712034))
>>678324285
Для Python даже не буду промежуточные результаты считать по заданному модулю, для языков без встроенной поддержки длинных чисел это сделать придётся.