algorithm - N と互いに素な数を法とする修正階乗 N を見つける

Question

2 つの数Nとが与えられたときp、 をと で割っkたものの最大べき乗をとします。とは余素です。pp^kN!d = N!/(p^k)dp

どうすれば見つけられますd mod pか? N!が高いと非常に高くなるため、直接反復は実用的ではありませんN。式を見つけるには、より効率的なアルゴリズムが必要です。

Answer 1

O(N) アルゴリズムは次のとおりです。

int d=1;
for(int i=1;i<=N;++i)
{
    d*=i;
    while(d%p==0)
      d/=p;
    d=d%p;
}

膨大な数を保存する必要がないため、許容される場合があります。O(p) アルゴリズムは可能だと思います (数値は k*p ごとに繰り返されるため) が、コードはもう少し複雑になります。