Как оптимизоровать поднятие в степень на Python?

Question

[hellcaster]

Привет. Я знаю, что вопрос капец какой странный, но сейчас объясню. На этом сайте собраны разные задачи и одна из них

Поднести число в степень другого и вывести на экран. Если число больше 1000000000 — вывести -1

Вроде нет ничего сложного, но все заключается в том, что на 18 тесте появляется ошибка Time Limit. Как ее обойти? Сначала я написал алгоритм на Java и он замечательно прошел, но на Python почти такой же не хочет((

Python

n, k = input().split()
n, k = int(n), int(k)
result = n ** k

print(-1 if result > 1000000000 else result)

Java

//package main;

import java.util.Scanner;

public class main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		double n = scanner.nextInt();
		double k = scanner.nextInt();
		double res = Math.pow(n, k);
		
		if (res > 1000000000) {
			System.out.println(-1);
		} else {
			System.out.println((int) res);
		}
	}
}

Comments

[Сергей Горностаев]

Сравнительно недавно на Тостере уже задавали вопрос про это.

[hellcaster]

Сергей Горностаев, извините, я не видел

[Сергей Горностаев]

muryn.official, нашёл. Может поможет чем: Как вычислить 9**(9**9) не потратив на это огромное количество времени?

Answer 1

[Farwisdomer]

https://en.wikipedia.org/wiki/Exponentiation_by_sq...

Answer 2

[Антон Федорян]

ужоснах

n, k = map(int, input().split())

if n == 0:
    result = 0
elif k == 0:
    result = 1
else:
    result = n
    for _ in range(1, k):
        if result < 1000000000:
            result *= n
        else:
            result = -1
            break

print(result)

Как тебе такое, Илон Маск?

Comments

[hellcaster]

Илону Маску не понравилось, так как в 12 тесте Worng answer

[Антон Федорян]

ограничения на числа n и k есть?

[hellcaster]

Антон Федорян, если дописать

if result * n < 1000000000:
    result *= n
  else:
    print(-1)
    exit()

ошибка будет на 17 тесте

[Антон Федорян]

номер задачи подскажи

[hellcaster]

Антон Федорян, в описание кликните на ссылку

[Антон Федорян]

Accepted

def power(n, k):
    if n == 1 or k == 0:
        return 1

    if n > 31621 and k > 2:
        return -1

    result = 1
    for _ in range(k):
        result *= n
        if result > 1000000000:
            return -1
            
    return result


print(power(*map(int, input().split())))

[U235U235]

if k*math.log10(n)>9.0:
     return -1
else:
     return n**k

Answer 3

[Иван Мельников]

Как вариант:

def my_pow(n, k):
    if k == 1:
        return n
    else:
        if k%2 == 1:
            return n*my_pow(n, k-1)
        else:
            k = k//2
            return my_pow(n, k)*my_pow(n, k)

Подправить код под себя наверное и сами сможете.