c - 存储大基数 B 的最佳方法？

Question

存储大基数 B 的最佳方法是什么，以便可以高效地完成右移和检查最低有效位等操作？

其实我遇到过一道面试题是这么说的

Given two numbers N and K such that 0<=N<=1000 and 0<=K<=1000^1000. I need 
to check that whether N^N = K or not. For example:

if N=2 and K=4 , 2^2 = 4 so return true;
if N=3 and K=26 , 3^3 != 26 so return false

我在想的是，如果我考虑 base N number system，那么 N^N 将等同于 1 后跟 N 零 在里面。例如 - 对于 N = 2、2^2 = 100(以 2 为基数)，对于 N=3、3^3 = 1000(以 3 为基数)。然后我可以轻松地编写一个函数来判断是否 K = N^N。

int check(unsigned long int N, unsigned long int K) 
{
    unsigned long int i;
    for (i=0; i<N; i++) 
    {
        if (K%N != 0) //checking whether LSB is 0 or not in base N number system 
           return 0;
        K = K/N; //right shift K by one. 
    }
    return (K==1);
}

现在这个函数有两个主要问题:

1) An unsigned long int is not sufficient to store large numbers of range 0 
to 1000^1000.
2) The modulus and the division operations makes it every less efficient.  

为了提高效率，我正在寻找一些表示大基数 N 的方法，以便我可以高效地执行右移和检查最低有效位操作。有没有人遇到过这样的事情？或者有人知道任何其他有效解决此问题的方法吗？

Answer 1

要检查相等性，您实际上不必进行高精度算术 - 您可以使用 http://en.wikipedia.org/wiki/Chinese_remainder_theorem .找到足够多的素数以确保它们的乘积大于 N^N，然后依次检查 N^N 与 K 对每个素数取模。

在实践中，我可能会使用 Java BigInteger 包来进行原始计算。