Как решить задачу «Шестерки» с меньшими затратами памяти?

Question

[demon trigger]

Формулировка задачи:
Шестиклассница Эмма в последнее время увлеклась восточной культурой. Дома она носит ханьфу, старательно выводит кисточкой иероглифы и очень любит цифру шесть, которая в Китае символизирует гармонию и баланс.
Сегодня, сидя за обедом, Эмма задумалась, что получится, если число, состоящее из одних шестёрок, возвести в квадрат? Помогите ей перемножить эти числа. Поскольку результат может оказаться очень большим, выведите только одну цифру на интересующей девочку позиции.

Входные данные
Две строки входного файла INPUT.TXT содержат два натуральных числа: N – длина числа, состоящего из одних шестерок, и K – интересующая Эмму позиция в квадрате числа (1 ≤ N ≤ 10^9; 1 ≤ K ≤ 2×N).

Выходные данные
В выходной файл OUTPUT.TXT выведите одну десятичную цифру – ответ на задачу.

Ограничения:
Время: 1 сек.
Память: 32 Мб

Мое решение "в лоб" не проходит по лимиту памяти. У меня есть предположение, что нам не надо хранить весь этот огромный квадрат числа в памяти и его как то можно срезать на месте, но как это реализовать я не знаю.
Мой код:

n = str(int(int(input()) * '6') ** 2)
k = int(input())
print(n[k - 1])

Answer 1

[Griboks]

Выведите на экран квадраты различных чисел - увидите интересную закономерность. Далее формализуйте эту закономерность и выводите цифру уже из неё (там будет 3, 4, 5 либо 6).

Answer 2

[Mercury13]

Шаг 1. Что собой представляет 66666·6?

 ₃₃₃₃
 66666
×    6
------
399996

Таким образом, получается N+1 цифра: 3, N−1 девятка, и 6.

Шаг 2. Что собой представляет 66666²?

     66666
    ×66666
----------
    399996
   399996
  399996
 399996
399996
----------
4444355556

(Простите уж, был обломИЩЕ, так что вычислил на калькуляторе и без цифр переноса.)

Могут быть вопросы, если очередная сумма перескочит за 100 и перенос будет двузначным — но нет, тут всё в порядке. Посчитаем (при достаточной длине кучи шестёрок):
Десятая с конца (!) цифра — 9·9 + 6 + 8 [перенос] = 95, перенос 9
Одиннадцатая — 9·10 + 6 + 9 = 105, перенос 10
Двенадцатая — 9·11 + 6 + 10 = 115, перенос 11
Так что без вопросов, всё остаётся как было.

Дальше как-то сможете своими силами?

Answer 3

[Wataru]

Выведите 6^2, 66^2 и так далее. N до 20 хотя бы. Посмотрите на числа. Можете ли вы угадать цифру на заданной позиции без подсчета всего числа?

Подсказка, вы получите вот такие вот числа:

36
4356
443556
44435556
4444355556
444443555556
44444435555556
4444444355555556
444444443555555556
44444444435555555556
4444444444355555555556
444444444443555555555556
44444444444435555555555556
4444444444444355555555555556
444444444444443555555555555556
44444444444444435555555555555556
4444444444444444355555555555555556
444444444444444443555555555555555556
44444444444444444435555555555555555556
4444444444444444444355555555555555555556

Этот паттерн можно и доказать. Надо лишь представить возводимое в квадрат число как (10**n-1)2/3 и применить чуть-чуть элементарной алгебры, вроде формулы квадрата разности.