找出最大的数字x对于给定的y和n使得x ^ y< = n

问题描述

我需要找到给定y和n的最大值x，以使x ^ y< = n

I need to find a greatest number, x for given y and n such that x ^ y <= n

这里n可以是非常大的数字-1 <= n< = 10 ^ 10和1< = y< = 10 ^ 5

Here n can be very large number - 1 <= n <= 10^10and 1 <= y <= 10^5

for example :

for y = 5 and n = 1024
x ^ 5, then x = 4 (4 ^ 5 = 1024)

for y = 5 and n = 480
x ^ 5 , then x = 3 (3 ^ 5 = 243, 4 ^ 5 = 1024) - selecting lowest one, so x = 3

我写了一个小程序，但是我想要更有效的技术，因为n和y可能很大.

i have written a small program, But i want more efficient technique because n and y can be very large.

def get(y, n):

    x = 1
    while x ** y <= n:
        x += 1
    return x - 1

推荐答案

使用多精度算术库，例如gmpy2的iroot.

Using a multiple-precision arithmetic library, such as gmpy2's iroot.

>>> import gmpy2
>>> root, exact = gmpy2.iroot(n, y)

这只是第n个整数的根算法.即使对于大量的数据，它也应该是快速且正确的(通常情况下不能保证浮动).

This is simply an integer n-th root algorithm. It should be fast and correct even for huge numbers (something that floats cannot guarantee in the general case).

返回的第二个值是一个布尔值，它指示根是否正确.

The second value returned is a boolean which indicates if the root is exact or not.

>>> print(*gmpy2.iroot(1024, 5))
4 True
>>> print(*gmpy2.iroot(480, 5))
3 False

这篇关于找出最大的数字x对于给定的y和n使得x ^ y&lt; = n的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！