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.
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())
EDIT: 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;
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
For example, the shortest bit string length that includes all of bit strings of length 2(00, 01, 10, 11) is 5(11001).
My solution for this problem was 2^n + n - 1. (so I should calculate powers of 2, I think I'll use bit-shifting)
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.
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!).