快速幂取模就是在O(logn)内求出a^n mod b的值。
原理：a^b mod n=(a mod n)(b mod n)mod n
// 快速幂 (a^b)%n ll mod_mul(ll a, ll b, ll n){ ll res = 0; while (b){ if(b & 1) res = (res + a) % n; a = (a + a) % n; b >>= 1; } return res; } ll mod_exp(ll a, ll b, ll n){ ll res = 1; while(b){ if(b & 1) res = mod_mul(res, a, n); a = mod_mul(a, a, n); b >>= 1; } return res; }
版权声明：本文为博主原创文章，未经博主允许不得转载。
原文：http://www.cnblogs.com/ygdblogs/p/5373046.html