-6

计算以下表达式值的最快算法和代码实现是什么？

嗯！/ (q!) r

我的代码

public static double timesbyf(int n,int q,int qt,int qp1,int qp1t)
{
    int totaltimes=qt+qp1t;
    double ans=1.0d;
    for(int i=1;i<=totaltimes;i++)
    {
        if(i<=qt)
        {
            for(int j=q;j>0;j--)
            {
                ans=ans*((double)n/(double)j);
                n--;
            }
        }
        else
        {
            for(int j=qp1;j>0;j--)
            {
                ans=ans*((double)n/(double)j);
                n--;
            }

        }
    }
    while(n>0)
    {
        ans=(ans*n)%3046201;
        n--;
    }
    return ans;
}

也就是n!除以q! r倍。

给定 n ≤ 3 × 10 6且 q < n，并且保证 (q!) r将干净地整除 n!。

4

3 回答 3

5

由于您在 n 上有一个较低的上限，因此可以通过对范围 [1, 3 × 10 6 ] 中的所有数字进行因式分解来开始。有很多方法可以合理有效地做到这一点。一种方法是使用埃拉托色尼筛法或相关筛法找到小于 3 × 10 6的所有素数，然后使用 DP 算法：标记 1 仅将其自身作为素数分解，然后对每个数字 2, 3, 4, 5, 6, ..., 3 × 10 6，尝试将这些数字按顺序除以素数，直到找到一个能完全除的数字，剩下的为 r。然后，该数的素数分解将是 r 的素数分解，乘以您除以的素数。

一旦你对所有这些数字进行了素数分解，你就可以有效地计算 n 的素数分解！使用数字 1、2、3、...、n 的素数分解。为此，您只需将数字 1、2、3、...、n 的因式分解中相应素数的所有指数相加即可。您可以类似地计算 q! 的素数分解，然后通过将 q! 的素数分解中的所有指数相乘得到 (q!) r的素数分解。由 r.

一旦你有了这些素数分解，你就可以计算 n! / (q!) r只需对 n 的素因数分解中的所有指数进行成对减法！通过 (q!) r的素数分解中的相应指数。然后，您可以恢复 n 的值！/ (q!) r将所有这些数字相乘。

如果您需要一个准确的值，那么您可能会花费更多的工作将所有因素相乘而不是实际找到这些因素。如果您只需要以某个大素数为模的值，那么这种方法将非常有效并且会给您一个准确的答案，只要您在将所有因子相乘时乘以那个大素数即可。

希望这可以帮助！

于 2013-06-10T19:56:39.087 回答
1

我认为计算两个非常大的数字并希望商得出合理的结果是一个非常糟糕的主意。

从获取自然对数开始：

ln(n!/(q!)^r) = ln(n!) - r*ln(q!)

您可以使用gammaln()两个函数值，化简，然后取得exp()到您想要的结果：

value = exp(gammln(n+1) -r*gammln(q+1))

Numerical Recipes有一章很好地介绍了如何实现类似的功能gammln().

于 2013-06-10T20:10:40.097 回答
1

如果您确实需要标准类型的完整结果（而不是模数模数），我想提出另一种解决方案，例如 long。你可以跳过一些计算，知道它们会溢出。

  1. 第一种情况：n 很小，所以 q 很小（所以假设它整除 n！），计算很容易，例如使用 @templatetypedef 答案。

  2. 第二种情况 n 大而 q 相对于 n 小：结果是无穷大。要确定 q 是否相对于 n 较小，请使用斯特林公式。因此，如果：的结果
    exp((n*ln(n)-n)/(q*ln(q)-q)^r))
    是Infinity双重计算，则无需实际计算结果。尤其是当假设您想要很长的确切结果时。

  3. 第三种情况：n 很大，q 也很大。@templatetypedef 也适用。

显然，如果您不需要确切的结果，您可以在 n 和 q 足够大时简单地使用斯特林近似。更准确地说，使用Ramanujan 的版本。

于 2013-06-10T21:58:16.323 回答