快速算法计算n!/(q!)^ r

Question

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

N!/(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 ⁶并且q <n,并且保证(q!)^r将干净地划分n!.

Answer 1

由于n的上限较低,因此可以通过将[1,3×10 ⁶ ] 范围内的所有数字分解来开始.有很多方法可以合理有效地完成这项工作.一种方法是使用Eratosthenes的筛子或相关的筛子找到小于3×10 ^6的所有素数,然后使用DP算法:标记1仅将其自身作为主要因子分解,然后对于每个数字2,3,4,5,6,...,3×10 ⁶,尝试按顺序将这些数字除以质数,直到找到一个干净分割,留下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将所有这些数字相乘.

如果您需要一个确切的值,那么您可能会花费更多的工作将所有因素相乘而不是实际找到这些因素.如果你只需要一个大模数的模数值,那么这个方法将非常有效并且会给你一个确切的答案,只要你通过将所有因子相乘的那个大的素数来修改.

希望这可以帮助!