C# 的标准库是否有简单的方法来检查一个数字是否是另一个数字的幂？

Question

我正在尝试查看是否有一个好的方法来查找给定 ints b 和 n 是否存在一个 int a 这样的a^n=b。换句话说，比我在下面写的糟糕解决方案更有效

private static bool HasBase(int b, int n)
{
    for(int a = 1; a <= int.MaxValue; ++a)
    {
        int pow = Power(a, n);
        if(pow == b)
            return true;
        else if(pow > b)
            return false;
    }
    return false;   
}

private static int Power(int a, int n) 
{
    return Enumerable.Range(a, n).Aggregate(1, (prev, cur) => prev * cur);
}

Answer 1

它有Math.log(double, double) 函数，它在第二个数字的基数中找到第一个数字的对数。如果那是完整的，那就是一种力量。例如，如果我想知道 x 是否是 2 的幂，我可以这样写：

bool isAPower = (Decimal)(Math.Log(x,2))%1==0;

也就是说，取x的对数底数2，除以1求余数。如果 mod 为 0 则为真，如果不为 0 则为假。

Answer 2

您可以找到b的所有因数，并检查同一个因数是否只重复n或xn次。因为 x^n*y^n = (xy)^n = a^n 或 x^(2n) = (xx)^n = a^n.

public static bool HasBase(int b, int n)
{
    // find all factors of b
    var factors = new List<int>();
    var dividers = Enumerable.Range(2, (int)Math.Round(Math.Sqrt(b) + 1)).GetEnumerator();
    dividers.MoveNext();
    while (true)
    {
        if (b % dividers.Current != 0)
        {
            if (dividers.MoveNext())
                continue;
            else
                break;
        }

        b /= dividers.Current;
        factors.Add(dividers.Current);
    }

    // if the base of each power can be divided by 3, a^n=b should be true.
    return multiples
        .GroupBy(x => x)
        .All(g => g.Count() % 3 == 0)
}

Answer 3

原题题目和正文有出入。假设文本是正确的，OP 想要在给定 a、b 和 X^a == b 的情况下找到 X。这是一个用于执行此操作的粗略算法，但它不是整数完美的。使用任何内置数学函数执行此类计算时，总会出现浮点错误。唯一的选择是执行一些计算密集型循环。

// given
int value = ...;
int power = ...;

// calculate the [power]th root of [value]
var root = value >= 0
    ? Math.Pow(value, 1d / power)
    : Math.Abs(power % 2) == 1
        ? -Math.Pow(-value, 1d / power)
        : Double.NaN;

// determine if [root] is an int
var root_is_int = Math.Abs(root - Math.Round(root)) <= Double.Epsilon;

请注意，除了由舍入误差引起的潜在问题外，这适用于 value 和 power 的所有值——正数、负数和零。

C# 的标准库是否有简单的方法来检查一个数字是否是另一个数字的幂？

Does the standard library of C# have an easy way to check whether a number is a power of another number?

.net

c#

algorithm