No.434

$S$ の大きさを $N$, $S$ の各要素を $a_i$ ($i \leq 1 \leq N$) として, 最終的な数値 (繰り上がり部分の処理なし) を $x$ とすると, $S$ の処理はパスカルの三角形の逆向きであることを考えると,

$$x = \sum_{i=1}^N {}_NC_i a_i$$

となる.

ある値 $x$ の繰り上がり処理後の値を $f(x)$ とすると,

$$f(x+y) = f(x) + f(y) \\ f(xy) = f(x)f(y)$$

が成り立つ. よって加算、乗算においてはその都度繰り上がり処理を適用してもよい.

${}_NC_i$ の計算はまともにやろうとすると除算が発生するのでこの方法が使えない.

そこで乗算/除算の各要素を素因数分解して, どの素因数が何回掛けられるかを管理する. ただし, このままでは素因数の数が多くなってしまうが, 最終的には掛け算に使うだけなので素因数も繰り上がり処理をしてしまえばいい.