!n mod p（混乱の数）where n ≤ 2∗10^8を実装する簡単な方法はありますかp？p < 1000
単純なアプローチが機能しないように、プログラムは高速に実行する必要があります。
2 に答える
8
!n mod pの周期で周期的であることがわかり2pます。!n mod pしたがって、として計算できます!(n mod 2p) mod p。これは、 derangements の再帰式で行い!n = (n-1) (!(n-1) + !(n-2))ます。
証明のために：
!(p+1) = 0 mod p混乱の再帰関係によって、 を観察します。- p を法として動作
!(n+p) = !p * !nします (これは、前の観測を使用して帰納的に証明できます)。 - それを観察して
!p = -1 mod pください。ウィキペディアでは次の式を提供して!n = n! - Sum[(n choose i) * !(n-i), i=1..n]いますi=n。 - と結論付け
!(n+2p) = !p !p !n = !n mod pます。
証明から、が より小さい!n = ± !(n mod p) mod p場合、符号が正である場所を実際に計算できることがわかります。n mod 2pp
于 2012-10-16T12:40:15.977 に答える
0
再帰的な式 ( !n = (n - 1) (!(n-1) + !(n-2))) があるのに、「剰余の乗算p」と「剰余の剰余」の演算を実装してみませんpか?
于 2012-10-16T12:02:20.460 に答える