龟速乘

$$ 将a\times b看成b个a相加 $$

$$ 将b进行二进制拆分为(b_1b_2b_3\dots b_n)_2 $$

$$ a\times b=a\times(2^{b_1}+2^{b_2}+2^{b_3}+\dots+2^{b_n}) $$

AcWing 90. 64位整数乘法 原题链接

求 aa 乘 bb 对 pp 取模的值。

输入格式

第一行输入整数aa，第二行输入整数bb，第三行输入整数pp。

输出格式

输出一个整数，表示a*b mod p的值。

数据范围1≤a,b,p≤10181≤a,b,p≤1018

输入样例：

3
4
5

输出样例：

2

    private static long quickAdd(long a, long b, long p) {
        long res = 0L;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = (res + a) % p;
            }
            a = (a + a) % p;
            b >>= 1;
        }
        return res;
    }
    public static void main(String[] args) {
        long a = in.nextLong();
        long b = in.nextLong();
        long p = in.nextLong();
        long res = quickAdd(a, b, p);
        out.println(res);
        out.flush();
        out.close();
   }