c - 如何有效地计算功率

Question

给定一个函数，使得 f(N)=1^1*2^2*3^3.....N^N。我必须计算 f(N)/f(r)*f(N-r)。 下面给出了我的 C 代码，但它适用于小 N，例如 5 或 6。

#include<stdio.h>

unsigned long long power(long x, long y)
{
    unsigned long long temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

int main(){
    unsigned long long N,M,Q,r[100001],j;
    int t,i;
    scanf("%d",&t);
    while(t--){
        scanf("%llu%llu%llu",&N,&M,&Q);
        for(i=0;i<Q;i++)
            scanf("%llu",&r[i]);
        for(i=0;i<Q;i++){
         unsigned long long mult=1;
           for(j=2;j<=N;j++){
              mult=mult*(power(j,j));
        }
           unsigned long long mult1=mult;
            mult=1;
          //unsigned long long ans=mult/((power(r[i],r[i]))*(power((N-r[i]),(N-r[i]))));
            for(j=2;j<=r[i];j++)
                mult=mult*(power(j,j));
            unsigned long long mult2=mult;
            mult=1;
            for(j=2;j<=N-r[i];j++)
                mult=mult*(power(j,j));
            unsigned long long mult3=mult;
           mult=1;
            unsigned long long ans=mult1/(mult2*mult3);
            printf("%llu\n",ans%M);
        }
    }
    return 0;
}

假设，f(5)=1^1*2^2*3^3*4^4*5^5=86400000。如果N非常大N<=10^5。那么我如何存储这样的一个很大的值。任何人都可以给我一种有效的算法来找到该值并将其存储在任何数组中。提前致谢。

Answer 1

对于无符号整数指数，它大多只是重复乘法的简写(例如，x^9 是 x*x*x*x*x*x*x*x*x).

为了有效地计算它(减少乘法次数)，您可以使用临时计算。例如，对于 x*x*x*x*x*x*x*x*x，您可以计算 y = x*x 并执行 y* y*y*y*x 代替；这是 5 次乘法而不是 8 次。您也可以执行 y = x*x 然后 z = y*y 然后 z*z*x > 将其减少到 4 次乘法。

事实证明，二进制非常棒，可以非常轻松地找到所需的最少乘法次数 - 指数的二进制数字告诉您。

更具体地说，(对于无符号整数指数，忽略溢出)这有效:

    result = 1;
    temp = x;
    while( exponent != 0) {
        if( (exponent & 1) != 0) {
            result *= temp;
        }
        exponent >>= 1;
        temp *= temp;
    }
    return result;

当然，溢出会是一个问题。对于大数字，您将需要某种可用于乘法的“大整数”代码(其中 temp 和 result 变量都是“大整数”)。

“大整数”通常只是一个(可变长度)整数数组，其中数组的每个元素代表大基数中数字的一位数字(例如，32 位数字的“基数 4294967296”)。我相信如果您想自己实现乘法和除法的算法，您可以找到它；或者一个合适的 C 库(如果没有的话)。

另一种选择是使用浮点。除了近似值之外，我不会推荐这样做，因为在处理大数时，您会得到精度损失(并且对于“非常大的数”，您仍然会出现溢出)。