题解 | #快速乘#

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        long a;
        long b;
        long p;
        while (n-- > 0) {
            a = input.nextLong();
            b = input.nextLong();
            p = input.nextLong();
            if (a > b) {
                System.out.println(cal(a, b, p));
            } else {
                System.out.println(cal(b, a, p));
            }

        }
    }

    public static long cal(long a, long b, long p) {
        long res = 0;
        //a*b=b个a相加 = b/2个（a+a）相加……
        while (b > 0) {
            if (b % 2 == 1) {
                b--;
                res = (res + a) % p;
            }
            b /= 2;
            a = (a + a) % p;
        }
        return res;
    }
}