快速幂取余

转载自https://www.cnblogs.com/vongang/archive/2012/03/15/2398626.html

 比较高效的求a*b% n 和 ab %n 的函数，这里都是用到二进制思想，将b拆分成二进制，然后与a相加（相乘）

 比如A^19 => （A^16）*（A^2）（A^1），显然采取这样的方式计算时因子数将是log(n)级别的(原来的因子数是n)，不仅这样，因子间也是存在某种联系的，比如A^4能通过(A^2)(A^2)得到，A^8又能通过(A^4)*(A^4)得到，这点也充分利用了现有的结果作为有利条件。下面举个例子进行说明：

现在要求A^156,而156(10)=10011100(2)

也就有A^156=>(A^4)(A^8)(A^16)*(A^128) 考虑到因子间的联系，我们从二进制10011100中的最右端开始计算到最左端。

例如：

//a^b % n
long long mod_exp(long long a,long long b,long long n){
    long long res = 1;
    while(b)
    {
        if(b&1)
            res=res*a % n;
        b>>=1;
        a=a*a % n;
    }
    return res;
}

同理：

// a * b % n
//例如: b = 1011101那么a * b mod n = (a * 1000000 mod n + a * 10000 mod n + a * 1000 mod n + a * 100 mod n + a * 1 mod n) mod n 

long long mod_mul(long long a, long long b, long long n) {
    long long res = 0;
    while(b) {
        if(b&1)    res = (res + a) % n;
        a = (a + a) % n;
        b >>= 1;
    }
    return res;
}