题解 | #排序#

总结：
本题与快速幂类似，存在两个难点：1.计算过程中数值过大 2.多个相加特别大时耗时长
难点1：

(a+b)%p = ((a%p)+(b%p))%p

利用上述公式可以解决问题1
难点2：
可以根据b为奇数或偶数，可以将其转为加法，将b=b/2,a=a*2可以减少大数加法

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        for(int i=0;i<n;i++){
            String[] line = sc.nextLine().split(" ");
            int a = Integer.parseInt(line[0]);
            int b = Integer.parseInt(line[1]);
            int p = Integer.parseInt(line[2]);
            int res = 0;
            while(b>0){
                if((b&1)==1)//b为奇数
                    res =(res+a)%p;
                a = (a*2)%p;
                b = b>>1;
            }
            System.out.println(res);
            res = 0;
        }

    }
}