Shashank - 8 months ago 53

C Question

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)`

`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()`

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.

Source (Stackoverflow)