如何在不适合任何语言的数据结构大整数工作 [英] How to work on big integers that don't fit into any of language's data structures

问题描述

我试图解决一个程序设计大赛的preliminary问题和我有计算和打印一些非常大的整数的问题2（如100！2 ^ 100）。

I'm trying to solve a programming contest's preliminary problems and for 2 of the problems I have to calculate and print some very big integers(like 100!, 2^100).

我也需要一个快速的方法来计算这个大整数的权力。

I also need a fast way to calculate powers of this big integers.

您可以咨询我一些这方面的算法或数据结构？（顺便说一句，我读I2C接口和实现任意precision算术部分，但它并没有帮助POW（））

Can you advice me some algorithms or data structures for this?(btw, I read C Interfaces and Implementations 'arbitrary precision arithmetic' section but it doesn't help for pow())

编辑：我想通过幂平方方法和位移将电源工作，但我也需要一个快速的方法来计算阶乘这个整数。谢谢你。

I think exponentiation by squaring method and bit-shifting will work for power but I also need a fast way to calculate factorials for this ints. Thanks.

EDIT2：对于那些有兴趣谁;

For those who are interested;

查找包括与长度为N的所有位串最短位字符串长度（对不起，我的英语，我举一个例子）。 N'LT = 10000

Find the shortest bit string length that includes all bit strings with length N (sorry for my english, I'll give an example). N <= 10000

例如，最短比特串长度，包括所有长度为2位串的（00，01，10，11）是图5（11001）

For example, the shortest bit string length that includes all of bit strings of length 2(00, 01, 10, 11) is 5(11001).

我对这个问题的解决方案是2 ^ N + N - 1。（所以我应该计算2的权力，我想我会用位移）

My solution for this problem was 2^n + n - 1. (so I should calculate powers of 2, I think I'll use bit-shifting)

其他问题是，鉴于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＆LT; = N＆LT; 2 ^ 63。我们将计算MOD 1000000007的anwser。

Other problem is, given the 2 lengths, find how in how many different ways you can reach the length N. For example, the input is 10, 2, 3. Then you should reach 10 with 2 and 3(for example, 2+2+2+2+2, 2+2+3+3, 3+2+2+3, 3+3+2+2...). 1 <= N < 2^63. We will calculate the anwser in mod 1000000007.

我的解决办法是，2倍+ 3Y = N时，那么，X =（N - 3Y）/ 2。 y的从0到2 * N / 3，如果x是一个整数，那么，我应该算广义置换为这个X和Y，总+ =（X + Y）！ /（X！* Y！）。

My solution was, 2x + 3y = N, so x = (N - 3y) / 2 . For y from 0 to 2*N / 3, if x is an integer, then I should calculate generalized permutation for this X and Y, total += (x+y)! / (x!*y!).

推荐答案

有关 POW 用整数的按平方幂

这篇关于如何在不适合任何语言的数据结构大整数工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！