Я для таких задач всегда предпочитал пользоваться внешними библиотеками мат. функций. Топорный алгоритм в виде деления на k работает очень медленно, а те как-то оперируют ими так, что время выполнения получается сильно меньше, если в том-таки Питоне проверять.