Shashank Shashank - 1 month ago 10
C Question

Calculating and printing (2^N-1) mod (10^9 + 7) for large N in C

I have a certain problem where I'm given a list of T numbers (T is the first line of the input) called N, and I must print out

((2^N)-1)%(10^9+7)
for each of the numbers. The following constraints apply:

1 ≤ T ≤ 100
1 ≤ N ≤ 100000000


I'm getting the right answer for low integers, but not for high ones. I think it has something to do with the
pow()
function in math.h but I'm unsure.

Here is my code:

#include <stdio.h>
#include <math.h>

int main(void) {
unsigned int t, i;
long long unsigned int ans, n, m = 1000000007;
scanf("%u", &t);
for (i = 0; i < t; ++i) {
scanf("%llu", &n);
ans = ((long long unsigned int)pow(2,n)-1)%m;
printf("%llu\n", ans);
}
return 0;
}


So basically when I give my program this input:

6
1
2
3
4
5
100000000


I get the output:

1
3
7
15
31
582344007


The first 5 lines of my output are correct but I want to get 494499947 for the last line.

See here for the wolfram alpha output which gives the correct answer.

Sorry if my question is trivial, I'm still learning the details of C.

Answer

The result of pow(2, 100000000) is over 30 million digits long. It cannot be converted to an integer type (even long long unsigned int) - it's way too big!

You will need to use modular exponentiation to get an accurate result here.

Comments