快速幂快速乘

int ，long，long long的范围

http://www.cnblogs.com/kuangbin/archive/2011/07/23/2115001.html

unsigned   int   0～4294967295
int   2147483648～2147483647
unsigned long 0～4294967295
long   2147483648～2147483647
long long的最大值：9223372036854775807
long long的最小值：-9223372036854775808
unsigned long long的最大值：18446744073709551615

__int64的最大值：9223372036854775807
__int64的最小值：-9223372036854775808
unsigned __int64的最大值：18446744073709551615

快速幂：二进制

 1 ll fastpow(ll a, ll b, ll mod)
 2 {
 3     ll ans=1,temp=a%mod;
 4     while(b)
 5     {
 6         if(b&1) ans=(ans*temp)%mod;
 7         b>>=1;
 8         temp=temp*temp%mod;
 9     }
10     return ans;
11 }

有时 a和b都很大，乘一次就可能爆long long ，此时要用快速乘。

例如这题：http://acm.hdu.edu.cn/showproblem.php?pid=5187

 1 #include<cstdio>
 2 #include<cstring>
 3 #define ll long long
 4 ll fastmul(ll a,ll b,ll m)
 5 {
 6     ll ans=0,temp=a%m;
 7     while(b)
 8     {
 9         if(b&1) ans=(ans+temp)%m;
10         b>>=1;
11         temp=(temp*2)%m;
12     }
13     return ans;
14 }
15 ll fastpow(ll a,ll b,ll m)
16 {
17     ll ans=1,temp=a%m;
18     while(b)
19     {
20         if(b&1) ans=fastmul(ans,temp,m);
21         b>>=1;
22         temp=(fastmul(temp,temp,m));
23     }
24     return ans;
25 }
26 
27 int main()
28 {
29     ll x,p;
30     while(scanf("%lld%lld",&x,&p)!=EOF)
31     {
32         if(x==1)
33         {
34             if(p==1) puts("0");
35             else puts("1");
36         }
37         else
38         printf("%lld
",(fastpow(2,x,p)-2+p)%p);
39     }
40 }