高次方求模（二分法） nyoj102

//eg：a^14= (a^7)^2 = ( (a^3)^2*a )^2
//求(n^p)%M
#define M 10003
int PowMod(int n, int p)
{
 int result = 1;
 while (p > 0)
 {
  if (p&1)
  {
   result = (result*n) % M;
  }
  p /= 2;
  n = (n*n) % M;
 }
 return result;
}
//求(a^b)%c 注意long long 不能取余，下面的代码应改进
long long power(long long a,long long b,long long c)
{
    long long d=1;
    while(b>0)
    {
         if(b&1)d=(d*a)%c;
         b/=2;
         a=(a*a)%c;
    }
    return d;
}