使用基本数据类型计算 C++ 中的阶乘项

Question

我正在解决一个编程问题，最后问题归结为计算以下项：

n!/(n1!n2!n3!....nm!)
n<50000
(n1+n2+n3...nm)<n

我得到的最终答案将适合 8 个字节。我正在使用 C++。我应该如何计算这个。我能够想出一些技巧，但没有具体和概括的东西。

编辑：我不想使用外部库。

编辑1：添加的条件和结果肯定是 64 位 int。

Answer 1

你可以做的是利用对数的性质：

log(AB) = log(A) + log(B)

log(A/B) = log(A) - log(B)

和

X = e^(log(X))

因此您可以先计算数量的对数，然后取幂：

log(N!/(n1!n2!...nk!)) = log(1) + ... + log(N) - [log(n1!) - ... log(nk!)]

然后扩展 log(n1!) 等等，所以你最终会根据单个数字的对数来编写所有内容。然后取结果的指数以获得阶乘的初始值。

作为@T.C。提到过，这种方法可能不太准确，尽管在典型情况下你会减少很多条款。或者，您将每个阶乘扩展到一个列表中，该列表将术语存储在其产品中，例如6! 将存储在列表 {1,2,3,4,5,6} 中。您对分母项执行相同的操作。然后你开始删除公共元素。最后，您可以采用 gcd 并将所有内容简化为互质因子，然后计算结果。

Answer 2

如果结果保证为整数，请使用因式分解。

通过theorem of Legendre，你可以用(2,n)范围内素数的指数序列来表达所有这些阶乘。

用分子中的分母中的阶乘的指数减去阶乘的指数，您将得到整个商的指数。然后计算将减少到永远不会溢出 8 字节的素数乘积。

例如，

25! = 2^22.3^10.5^6.7^3.11^2.13.17.19.23
15! = 2^11.3^6.5^3.7^2.11.13
10! = 2^8.3^4.5^2.7

产量

25!/(15!.10!) = 2^3.5.11.17.19.23 = 3268760

例如，3 的指数由

找到

25/3 + 25/9 = 10
15/3 + 15/9 = 6
10/3 + 10/9 = 4

Answer 3

如果所有输入（不一定是输出）都是整数，您可以尝试计算素数。您创建一个大小为 sqrt(n) 的数组，并用 n 中每个质因数的计数填充它：

vector <int> v = vector <int> (sqrt(n)+1,0);
int m = 2;
while (m <=n) {
    int i = 2;
    int a = m;
    while (a >1) {
        while (a%i ==0) {
            v[i] ++;
            a/=i;
        }
        i++;
    }
    m++;
}

然后迭代 n_k (1 <= k <= m) 并减少每个质因数的计数。除了将 v[i]++ 替换为 v[i] -- 之外，这与上面的代码几乎相同。当然需要用之前得到的vector v来调用。

之后向量 v 包含表达式中素数的列表，您只需要将结果重建为

int result = 1;
for (int i = 2; i < v.size(); v++) {
    result *= pow(i,v[i]);
}
return result;

注意：您应该使用 long long int 而不是上面的 int，但为了简单起见，我坚持使用 int

Edit : 正如另一个答案中提到的，最好使用勒让德定理来更快地填充/取消填充向量 v。

使用基本数据类型计算 C++ 中的阶乘项

Calculate this factorial term in C++ with basic datatypes

c++

algorithm

factorial