如何处理不适合任何语言数据结构的大整数
我正在尝试解决编程竞赛的初步问题，对于其中的两个问题，我必须计算和打印一些非常大的整数(如100!，2^100)。
我还需要一种快速的方法来计算这个大整数的幂。
你能给我一些关于这方面的算法或数据结构的建议吗？(顺便说一句，我读过“C接口和实现”的“任意精度算术”一节，但它对pow()没有帮助)
编辑:我认为平方方法和位移位的幂运算将会有效，但我也需要一种快速的方法来计算这个整数的阶乘。谢谢。
EDIT2:对于有兴趣的人；
找到包含所有长度为N的比特串的最短比特串长度(对不起，我会举个例子)。N <= 10000
例如，包括长度为2(00，01，10，11)的所有比特串的最短比特串长度是5(11001)。
我对这个问题的解决方案是2^n +n- 1 (所以我应该计算2的幂，我想我会使用位移位)
另一个问题是，给定两个长度，找出有多少种不同的方法可以达到长度N。例如，输入是10，2，3。然后你应该在2和3之间达到10 (例如，2+2+2+2+2，2+2+3+3，3+2+2+3，3+3+2+2...)。1 <= N< 2^63。我们将以mod 1000000007计算价格。
我的解是，2x + 3y = N，所以x= (N - 3y) /2。对于Y从0到2*N / 3，如果x是一个整数，那么我应该计算这个X和Y的广义排列，总+= (x+y)！/ (x!*y!)。
回答 7
Stack Overflow用户
发布于 2011-04-05 05:08:45
对于包含整数的pow，exponentiation by squaring
Stack Overflow用户
发布于 2011-04-05 05:06:48
为了计算幂，使用二分法算法，该算法使用指数的二进制表示，并减少了乘法次数。数据结构只是一个整数数组
Stack Overflow用户
发布于 2011-04-05 05:36:46
您可能想看看加密程序的实现(特别是我首先想到的是GnuPG )。原因是加密函数也使用非常大的整数(所谓的MultiPrecision整数-MPI)。这些MPI以这样一种方式存储，即前2个字节告诉整数的大小，后面的字节如何存储值。
GPG是开源的，看看吧:)
https://stackoverflow.com/questions/5544293
复制相似问题
腾讯云开发者
