水

我们知道对于幂运算有： ab%k=(a%k)(b%k)%k
如： 5 * 6 % 4 = （1+4）（2+4）% 4 = 1 * 2 % 4
因为 1 * 4 和 2 * 4 和4 * 4模4都为0

位运算加速

//b^p%k
void mi(){
   long long m=1;
   if(!p) m=0; 
   while(p>0){	
   if(p&1)    m=m*b%k;     //p%2!=0;
   p>>=1;         // p/=2
    b=b*b%k;
   }
   printf("%ld",m);
}