c - 如何处理不适合任何语言数据结构的大整数

Question

我正在尝试解决编程竞赛的初步问题，对于其中的 2 个问题，我必须计算并打印一些非常大的整数(例如 100!、2^100)。

我还需要一种快速的方法来计算这个大整数的幂。

你能为此建议我一些算法或数据结构吗？(顺便说一句，我阅读了 C 接口(interface)和实现的“任意精度算术”部分，但它对 pow() 没有帮助)

编辑:我认为通过平方方法求幂和移位对幂有用，但我还需要一种快速方法来计算此整数的阶乘。谢谢。

EDIT2:对于那些有兴趣的人；

找到包含所有长度为 N 的位串的最短位串长度(抱歉我的英语不好，我会举个例子)。 N <= 10000

例如，包含长度为2(00,01,10,11)的所有位串的最短位串长度为5(11001)。

我对这个问题的解决方案是 2^n + n - 1。(所以我应该计算 2 的幂，我想我会使用位移)

另一个问题是，给定 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 。对于从 0 到 2*N/3 的 y，如果 x 是一个整数，那么我应该计算这个 X 和 Y 的广义排列，total += (x+y)!/(x!*y!).

Answer 1

对于带有整数的pow，exponentiation by squaring