模板

// 快速幂取模函数，计算 (a^k) % p
int qmi(int a, int k, int p) {
    int res = 1;
    while (k > 0) {
        if (k % 2 == 1)  // 如果 k 的最低位为1
            res = (LL)res * a % p;  // res = (res * a) % p
        k  = k / 2 ;  // k 右移一位，相当于 k = k / 2
        a = (LL)a * a % p;  // a = (a * a) % p，底数平方取模
    }
    return res;
}

本题题解

#include <iostream>

using namespace std;

typedef long long LL;

int modExp(string s,LL exp,LL mod){
	LL result = 1;
	
	LL x = 0;
	
	// 问题：把字符串转化为long long，不会超出longlong的范围吗？
	// 不会的，因为 每一步的最终结果都mod 
	for(int i = 0;i < s.size();i ++){
		x = (x * 10 +(s[i] - '0')) % mod;
	}
	
	// 快速幂取模函数，计算 (a^k) % p
	// 把这里的指数exp转化为二进制进行计算，提高运算速度 
	while(exp > 0){
		if(exp % 2 == 1){ // 如果 k 的最低位为1
			result = (result * x) % mod;
		}
		// 用result存储最终的答案，result = x*x*x*x*x*x*......
		 
		x = (x * x) % mod;
		exp = exp / 2;
	}
	return result;
}

int main(){
	string x;
	LL y,z;
	
	while(cin >> x >> y...