无需使用外部库即可优化处理极大数量的方法

Question

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

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

搜查,发现了GMP library http://gmplib.org/和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位数.我想到得到那些18位数而没有真正解决完整的n ^ n表达式.

有什么想法/建议吗？

Answer 1

// 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;
}