1

处理 n^n (1 ≤ n ≤ 10^9) 值的优化方式

我用过long long int，但它不够好，因为值可能是 (1000^1000)

搜索并找到了http://gmplib.org/GMP library 但BigInt class不想使用它们。我正在寻找一些数值方法来处理这个问题。

我需要打印的第一个和最后一个k (1 ≤ k ≤ 9) 位n^n

对于前k个数字，我得到如下所示（这样做有点丑陋）

num = pow(n,n);
while(num){
    arr[i++] = num%10;
    num /= 10;
    digit++;
}
while(digit > 0){
    j=digit;
    j--;
    if(count<k){
        printf("%lld",arr[j]);
        count++;
    }
    digit--;
}

并且对于最后k位使用num % 10^k如下所示。

findk=pow(10,k);
lastDigits = num % findk;
enter code here

k的最大值是9。所以我最多只需要18位数字。我想在没有真正解决完整的 n^n 表达式的情况下获得这 18 位数字。

任何想法/建议？

4

3 回答 3

5 
// note: Scope of use is limited.

#include <stdio.h>

long long powerMod(long long a, long long d, long long n){
// a ^ d mod n
    long long result = 1;
    while(d > 0){
        if(d & 1)
            result = result * a % n;
        a = (a * a) % n;
        d >>=1;
    }
    return result;
}

int main(void){
    long long result = powerMod(999, 999, 1000000000);//999^999 mod 10^9
    printf("%lld\n", result);//499998999

    return 0;
}
于 2013-05-21T08:38:02.837 回答
4

由于模算术的性质，找到最低有效位（最后 k 位）很容易，它说：(n*n)%m == (n%m * n%m)%m，因此BLUEPIXY显示的代码遵循平方方法的幂运算将适用于查找kLSD。

N^N现在，可以通过以下方式找到的最高有效数字（第 1 k 位） ：

 We know, 
 N^N = 10^(N log N)

所以如果你计算N log (N)你会得到一个这种格式的数字xxxx.yyyy，现在我们必须用这个数字作为10的幂，很容易理解，数字的xxxx或整数​​部分会在10之后添加xxxx零，这对于你！这意味着，如果您计算10^0.yyyy，您将获得您正在寻找的那些有效数字。所以解决方案将是这样的：

double R = N * log10 (N);
R = R - (long long) R; //so taking only the fractional part
double V = pow(10, R);
int powerK = 1;
for (int i=0; i<k; i++) powerK *=10;
V *= powerK;
//Now Print the 1st K digits from V
于 2013-05-21T11:31:58.287 回答
0

为什么不想使用bigint库？

bignum 算术很难正确有效地完成。您仍然可以通过研究该主题获得博士学位。

拳头，bigint 算术具有非平凡的算法

然后，bigint 实现通常需要一些在普通 C 中不易访问的机器指令（如带进位的加法）。

对于您的特定问题（ N N的前几位和最后几位），您最好还可以在纸上推理（使用算术定理）以降低复杂性。我不是专家，但我想这仍然是棘手的，可能比O(N)更复杂

于 2013-05-21T05:02:35.603 回答