Hi Abid,

Why don't you learn successive squaring algorithm? Using the pow() function has no need here. Look at the two following method for computing (b^p)%m efficiently even b, p, m all are quite large.

1st method is recursive and goes as Articuno told you, easy to understand:

Code: Select all

```
typedef unsigned long long i64;
inline i64 sqr(i64 n)
{
return n*n;
}
i64 bigmod(i64 b, i64 p, i64 m)
{
if (p == 0)
return 1;
if (p%2 == 0)
return sqr( bigmod (b,p/2,m)) % m;
return ((b % m) * bigmod( b,p-1,m)) % m;
}
```

2nd method is iterative and a bit faster, try to avoid recursion whenever you can:

Code: Select all

```
typedef unsigned long long i64;
i64 fast_mod_exp(i64 b, i64 p, i64 m)
{
i64 r = 1;
while(p>0)
{
if(p&1==1) r = (r*b)%m;
p >>= 1;
b = (b*b)%m;
}
return r;
}
```

I think it will help you.

**@@ ANYBODY TELL ME IF IT IS A SPOILER FOR THIS PROBLEM, I'LL REMOVE IT @@**
zobayer_1@live.com