modに対するアプローチ

Latest Author kroton 💸 /Date 2015-01-23 15:31:44 / Views 845
0 (Favした一覧ページは作成中です。)
分解してみる
例題: ${}_n \mathrm{C} _k \pmod{20}$ を求めよ。 ただし $0\leq k \leq n \leq 10^{6}$
${}_n \mathrm{C} _k \equiv \frac{n (n-1) (n-2) \ldots (n-k+1)}{k!} \pmod{20}$ なので $\{k!\}^{-1} \pmod{20}$ が計算できればよさそうですが
$k!$ と $20$ が互いに素になるかはわかりません。仮に互いに素でない場合は逆元が存在しないのでこのままでは解けません。
そこで $20 = 2^{2} \times 5$ であることに着目して
  • $n (n-1) (n-2) \ldots (n-k+1) = 2^{t_1}\times 5^{f_1}\times r_{1}$
  • $k! = 2^{t_2}\times 5^{f_2}\times r_{2}$
と分解してみます。すると答えは $2^{t_1 - t_2}\times 5^{f_1 - f_2}\times r_1 \times {r_2}^{-1} \pmod{20}$ になります。
いま $r_{2}$ に $2$ と $5$ は含まれていないので $r_{2}$ と $20$ が必ず互いに素になり逆元が計算できます。
中国人剰余定理
「$m_{1}, m_{2} \ldots m_{k}$ がどの2つも互いに素ならば
  • $x \equiv a_{1} \pmod{m_{1}}$
  • $x \equiv a_{2} \pmod{m_{2}}$
  • $\ldots$
  • $x \equiv a_{k} \pmod{m_{k}}$
をすべて満たす $x$ が $m_{1} m_{2} \ldots m_{k}$ を法として一意に存在する」というのが中国人剰余定理です。

$f(n) \pmod m$ を直接計算するのは難しい・大変である場合でも、$m = {p_1}^{e_1} {p_2}^{e_2} ... {p_k}^{e_k}$ と分解して
  • $ f(n) \equiv r_1 \pmod{{p_1}^{e_1}}$
  • $ f(n) \equiv r_2 \pmod{{p_2}^{e_2}}$
  • $ \ldots$
  • $ f(n) \equiv r_k \pmod{{p_k}^{e_k}}$
を計算できたのであればそれらから $f(n) \pmod m$ を計算することができます。

上の問題でいうと ${}_n \mathrm{C} _k \pmod{2^{2}}$ と ${}_n \mathrm{C} _k \pmod{5}$ が計算できれば ${}_n \mathrm{C} _k \pmod{20}$ を計算できることになります。
詳細は割愛しますが ${}_n \mathrm{C} _k \pmod{p^e}$ は前処理に $O(p^e)$ かけることで一回あたり $O(\log n)$ で計算することができます。
逆元を消してみる
  • $f(n, p) := n!$ のなかに素数 $p$ が何個含まれているか
上記を定義しておくと ${}_n \mathrm{C} _k \equiv 2^{f(n,2)-f(k,2)-f(n-k,2)} \times 3^{f(n,3)-f(k,3)-f(n-k,3)} \ldots \pmod{20}$ となります。
こうすると逆元というやっかいな操作を気にする必要がなくなります。
逆元を使った小ネタ
いま $2^{32}$ と互いに素な $b < 2^{32}$ を考えてみます。 互いに素なので当然 $b^{-1} \pmod{2^{32}}$ が計算できます。
ここで $2^{32}$ 未満の $b$ の倍数を考えてみると $0,\ b,\ 2b \ldots \lfloor \frac{2^{32}-1}{b} \rfloor b$ があります。これらに $b^{-1} \pmod{2^{32}}$ を掛け $2^{32}$ で余りを取ると $0, 1, 2 \ldots \lfloor \frac{2^{32}-1}{b} \rfloor$ になります。
また $n \not\equiv m \pmod{2^{32}} \Rightarrow nb^{-1} \not\equiv mb^{-1} \pmod{2^{32}}$ であるので $2^{32}$未満で $b$ の倍数でないものに $b^{-1} \pmod{2^{32}}$ を掛け $2^{32}$ で余りを取ると $\lfloor \frac{2^{32}-1}{b} \rfloor$ より大きくなります。
つまりこれを使うと掛け算のみで倍数判定を行うことができます。(C++のunsignedではオーバーフローすると0に巻き戻されるので余りを取るのと同じことになります。)
// 2^32未満で3の倍数かどうか判定する
bool is_3k(unsigned n){
  return n * 2863311531u <= 1431655765u;
}