大数取模

(A*B)%C=(A%C*B%C)%C

1.(A*B)%C

将B转化成二进制形式，-->A(2^0+2^1.....)%C-->A%C+2A%C+4A%C......

ps:B超出int表示范围时，转化成二进制，用数组表示

//二分法求（A*B)%C
typedef unsigned _int64 llong;
llong Modle(llong a,llong b,llong c)
{
llong d=0;
while(b)
{
if(b&1) d=(d+a)%c;
a=(a+a)%c;
b>>=1;
}
return  d;
}

一般来说，类似上题，用二分法：

int mod_exp(int a,int b,int c)
{
int d=1;
while(b)
{
if(b&1) d=(d*a)%c;
a=(a*a)%c;
b>>=1;
}

return d;}

int mod_exp(int a,int c)
{
a%=c;
int i=0,d=1,bi[30];
while(b&&i<30)
{
bi[i++]=b%2;
b=b/2;
}
for(;i>=0;i--)
{
d=(d*d)%c;
if(b[i]==1) d=(d*a)%c;
}
return d;
}