快速乘和改造快速幂

快速乘

​ 因为我们知道乘法有时候会溢出，即使是long也可能因为结果过大而溢出（当模数也是long类型时）。所以我们需要寻找一种能高效完成乘法操作并且不会爆 long 的算法，也就是快速乘。即不会溢出采用快速幂，会溢出采用快速乘。

//快速乘
//计算大数：a * b(mod modd) 10*(11)
public static long quickMultiple(long a,long b,long modd){
    long res = 0l;
    while (b!=0){
        if((b&1)==1) res = (res+a)%modd;
        a = (a << 1)%modd;
        b = (b >> 1);
    }
    return res;
}

快速幂改造

利用快速乘改造快速幂

//利用快速乘改造快速幂解决溢出问题
//计算a^n%p
public static long quickPowUseMul(Long a,Long n,Long p){
    long res = 1l;
    while (n!=0){
        if ((n&1)==1)   res = quickMultiple(res,a,p);
        n = n>>1;
        a = (a * a)%p;
    }
    return res;
}

典型例题

第十届蓝桥杯（省赛）试题E:RSA解密

g/?id=70878&compatibility=false)

参考材料

[1]快速乘总结