¿ìËÙÇóaµÄb´ÎÃݶÔcÈ¡Óà

¿ìËÙÃÝÈ¡Ä£ÀíÂÛ»ù´¡£º  ¼ÆËã a^b mod c ?
  ÓÉ(a x b) mod c=((a mod c) x b) mod c.
 ÎÒÃÇ¿ÉÒÔ½« bÏȱíʾ³É¾Í£º
   b=at2^t+at-1 2^t-1+……a02^0. (ai=[0,1]).
 ÕâÑùÎÒÃÇÓÉ a^b mod c=(a^(at2^t+at-12^t-1+…a02^0)mod c.
 È»¶øÎÒÃÇÇó  a^(2^(i+1))mod c=((a^(2^i))mod c)^2 mod c .ÇóµÃ¡£
 
¿ìËÙÃÝÈ¡ÓàµÄ³ÌÐò£º
 
long long BigMod(long long a,long long p,long long m)  //a^p%m
{
    if (a==0 || m==1)
        return 0;
    if (p==0)
        return 1;
    if (p%2)
        return ((a%m)*BigMod(a,p-1,m))%m;
    long long tmp=BigMod(a,p/2,m);
    return (tmp*tmp)%m;
}