4-1. N! の高速な計算 $N! = 1 \times 2 \times 3 \times 4 \times \cdots \times N$ を計算してみましょう。 $N!$ は場合の数を求める問題でよく出てきて、こんな感じのものが求まります。 $1, 2, ..., N$ が書かれたトランプのカードが 1 枚ずつあるとき、これを一列に並べる順番は何通りあるか? 例えば、$N = 13$ の場合 $13! = 6,227,020,800$ 通り、のように計算できます。 また、$N!$ は二項係数 $_NC_K$ を求めるのにも使われます。 $N!$ が求まれば、$_NC_K = N! \div K! \div (N-K)!$ で掛け算・割り算するだけで計算できますね。 $N$ 個の区別できるボールから $K$ 個を選ぶ方法は何通りか? これが $_NC_K$ になります。例えば、$N
![超高速!多倍長整数の計算手法【後編:N! の計算から円周率 100 万桁の挑戦まで】 - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/e82d9d2630526472e1b8b116f72ff7cb03b025ce/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-412672c5f0600ab9a64263b751f1bc81.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk3MiZoPTM3OCZ0eHQ9JUU4JUI2JTg1JUU5JUFCJTk4JUU5JTgwJTlGJUVGJUJDJTgxJUU1JUE0JTlBJUU1JTgwJThEJUU5JTk1JUI3JUU2JTk1JUI0JUU2JTk1JUIwJUUzJTgxJUFFJUU4JUE4JTg4JUU3JUFFJTk3JUU2JTg5JThCJUU2JUIzJTk1JUUzJTgwJTkwJUU1JUJFJThDJUU3JUI3JUE4JUVGJUJDJTlBTiUyMSUyMCVFMyU4MSVBRSVFOCVBOCU4OCVFNyVBRSU5NyVFMyU4MSU4QiVFMyU4MiU4OSVFNSU4NiU4NiVFNSU5MSVBOCVFNyU4RSU4NyUyMDEwMCUyMCVFNCVCOCU4NyVFNiVBMSU4MSVFMyU4MSVBRSVFNiU4QyU5MSVFNiU4OCVBNiVFMyU4MSVCRSVFMyU4MSVBNyVFMyU4MCU5MSZ0eHQtYWxpZ249bGVmdCUyQ3RvcCZ0eHQtY29sb3I9JTIzMjEyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTU2JnM9YmRlZDE1YjgwZDYyOTRmNmRiZjBmZjc0YTAxZTQ3NGY%26mark-x%3D142%26mark-y%3D57%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZoPTc2Jnc9NzcwJnR4dD0lNDBzcXVhcmUxMDAxJnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9MzYmdHh0LWFsaWduPWxlZnQlMkN0b3Amcz04NTIyOTAxMjZiOTkxZDk4NzE1ZmZlZWFjNjI3MTUxYg%26blend-x%3D142%26blend-y%3D486%26blend-mode%3Dnormal%26s%3D3dea6fc484f2b61d61b6d1c7070b9464)