c++ - 在C++中打印(2 ^ n的基础)/(2 ^ n -1)mod m

我们如何在C ++中存储和打印阶乘（2 ^ n）/（2 ^ n -1））mod1000000009。这里n可以大到20。当我尝试使用以下代码打印时，它显示分段错误n = 20
    ＃包括
    ＃包括
    使用名称空间std;

long int factorial(int n)
{
if(n<=1){return 1;}
else
return (n%1000000009)*(factorial(n-1))%1000000009;

}

int main()
{

int K;
long long int numofmatches=0;
long long int denominator=0;
long long int factor=0;
long long int times=0;
long long int players=0;
cin>>K;


if(K==1)
{
    cout<<2<<endl<<2<<endl;
    return 0;
}
else
{
    denominator=pow(2,K);
cout<<"Denominator="<<denominator<<endl;

numofmatches=factorial(denominator)%1000000009;

denominator-=1;
cout<<"numberofmatches="<<numofmatches<<endl;
cout<<"Denominator="<<denominator<<endl;

factor=numofmatches/denominator;
cout<<"Factor="<<factor<<endl;

while(times<=denominator)
{
cout<<(times*factor)<<endl;
++times;
}

}
return 0;
}

最佳答案

首先，请注意(2^n)! / (2^n-1)等于(2^n-2)! x 2^n。

现在，(2^20-2)!本身已经是一个非常庞大的数字。

相反，您可以做的是在每次乘法后用1000000009对中间结果取模：

#define MAX ((1<<20)-2)

unsigned long long res = 1;
for (unsigned int i=1; i<=MAX; i++)
    res = (res*i)%1000000009;
res = (res*(MAX+2))%1000000009;

如果要迭代n的所有值（介于1和20之间），则可以使用：

#define MAX_N 20

unsigned int arr[MAX_N+1] = {0};

void Func()
{
    unsigned int i = 1;
    unsigned long long res = 1;
    for (int n=1; n<=MAX_N; n++)
    {
        unsigned int max = (1<<n)-2;
        for (; i<=max; i++)
            res = (res*i)%1000000009;
        arr[n] = (unsigned int)((res*(max+2))%1000000009);
    }
}

顺便说一句，对于任何大于29的n，结果将简单地为0，因为(2^30-2)大于1000000009。

因此(2^30-2)!可被1000000009整除，因此(2^30-2)! mod 1000000009等于0。

关于c++ - 在C++中打印(2 ^ n的基础)/(2 ^ n -1)mod m，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22437393/