算法分析

快速幂与龟速乘法的对比
快速幂解决$a ^ b$ $mod$ $p$的问题，而龟速乘法解决$a * b$ $mod$ $p$的问题

本质上
快速幂：$a ^ b$ $mod$ $p$ $= a * a * a … * a % p$
龟速乘：$a * b$ $mod$ $p$ $= a + a + a … + a % p$

快速幂：从$a$ 算出 $a^2$, 再算出 $a^4$，$a^8$…(通过 $k$ 的二进制中哪些位需要加上该位的值，算出 $a^k$)
龟速乘：从$a$ 算出 $2 * a$, 再算出$4 * a$，$8 * a$…(通过 $k$ 的二进制中哪些位需要加上该位的值，算出$a * k$)

注意:Java 的同学还可以直接使用BigInteger算很大的值

时间复杂度 $O(logb)$

参考文献

算法提高课

Java 代码(龟速乘)

import java.util.Scanner;

public class Main {
    static long qadd(long a,long k,long p)
    {
        long res = 0;
        while(k > 0)
        {
            if((k & 1) == 1) res = (res + a) % p;
            k >>= 1;
            a = (a + a) % p;
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long a = scan.nextLong();
        long b = scan.nextLong();
        long p = scan.nextLong();
        System.out.println(qadd(a,b,p));
    }
}

Java 代码(BigInteger)

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        BigInteger a = new BigInteger(scan.next());
        BigInteger b = new BigInteger(scan.next());
        BigInteger p = new BigInteger(scan.next());
        System.out.println(a.multiply(b).mod(p));
    }
}