c++ - 具有大阶乘的数学(例如除法？)

Question

我正在尝试找出包含长度超过 50 的循环的 100 个数字的排列百分比。这涉及由具有大阶乘的除法组成的数学，无法用手很快完成，所以我需要诉诸编程。例如这些术语包含

(3!/100!)*((99!/3!) + (98!/2!) + (97!/1!) + (96!/0!))

我可以重新排列所有项以提供一个大数 (>2^64)，只需除以 100!得到我的答案。

我想了很多，对 C++ 还是个新手，我不确定如何对大数进行除法。通常，当我处理大阶乘时，我会将数字的数字输出到数组中并通过它进行乘法运算，但我不完全确定如何以这种方式进行除法运算。在 C++ 中处理大数数学的最佳方法是什么？

Answer 1

从方程式的结构(一个非常大的阶乘乘以一些具有大约相同大小的大阶乘的倒数)可以明显看出，可能会发生很多抵消。这意味着即使没有任何类型的计算，这个问题也可以通过一些非常简单的代数和一些额外的运气来解决。

让我们用一些无辜的小字母替换阶乘，以避免被大数字吓到。

0! = 1 根据定义和 1!=1 我们可以跳过这些值并使用以下替换:

a = 2!, b = 3!, v = 96!, w = 97!, x = 98!, y = 99!, z = 100!

这给了

(b/z)*(y/b + x/a + w + v)

展开

b*(y/b + x/a + w + v) * 1/z

展开分子(让我们使用一些 ASCII 艺术来提高易读性)

                      b*x
 y +  (b*w) + (b*v) + ---
                       a
 ------------------------
            z

把它全部压缩成一个分数

(a*y) + (a*b*w) + (a*b*v) + (x*b)
---------------------------------
             (a*z)

把它拆开

 a*y     a*b*w     a*b*v     x*b 
----- + ------- + ------- + -----
 a*z      a*z       a*z      a*z 

是的，看起来不错，我们可以把数字放回去

 2!*99!       2!*3!*96!       2!*3!*97!      3!*98!
--------- + ------------- + ------------- + ---------
 2!*100!       2!*100!         2!*100!       2!*100!

第一轮取消(可能已经在信函阶段完成)

  99!      3!*96!      3!*97!     3!*98!
------ + ---------- + -------- + --------
 100!       100!        100!      2!*100!

阶乘相互抵消，但只是部分抵消

第一步

 1         1*2*3        1*2*3     1*2*3
---  + ------------ + --------- + ------
100    97*98*99*100   98*99*100   1*2*99*100

第二步

 1           1            1          1
---  + ------------ + -------- + -------
100    97*98*33*50    98*33*50   2*33*50

共同点

97*98*33*50*2 + 100*2 + 100*97*2 + 100*97*98
--------------------------------------------
           100*97*98*33*50*2

通过因式分解 100 来稍微调整一下分子

97*98*33*50*2 + 100*(2*98 + 97*98)
----------------------------------
       100*97*98*33*50*2

部分

  97*98*33*50*2      100*(2*98 + 97*98)
----------------- + -------------------
100*97*98*33*50*2    100*97*98*33*50*2

取消

 1     2*98 + 97*98
--- + --------------
100   97*98*33*50*2

部分

 1        2*98             97*98
--- + -------------- + --------------
100   97*98*33*50*2    97*98*33*50*2 

取消

 1        1          1
--- + -------- + -------
100   97*33*50   33*50*2 

然后我们有 less 和去掉了 98。冲洗并重复直到找到最终结果:

  1
 ----
  97

是的，有时候一支锋利的铅笔和一张白纸就是您所需要的；-)