#include <iostream>
using namespace std;
#include <string>
#include <ctime>

#define MAX 100000

string answerqq(MAX, '0');//這個字符串決定了輸出答案位數的最大值。

string add(string a, string b)//算兩個字符串的加法，如“123456” + “111111” = “234567”；
{
	if(a == "")
		return b;
	else if(b == "")
		return a;

	if(a.length() < b.length())
	{
		string temp = a; 
		a = b;
		b = temp;
	}

	int input = 0, i = MAX - 1, lengtha = a.length(), lengthb = b.length(), temp;

	while(lengthb)
	{
		temp = a[--lengtha] + b[--lengthb] - 96 + input;

		answerqq[i--] = temp % 10 + 48;
		input = temp >= 10 ? 1 : 0;	
	}

	int te = lengtha , flag = 0;
	if(lengtha)
	{
		while(lengtha)
		{
			a[--lengtha] += input;

			input = 0;
			if(a[lengtha] > '9')
			{
				a[lengtha] = '0';
				input = 1;
			}

		}

		while(te)
			answerqq[i--] = a[--te];

		if(input == 1)
			answerqq[i--] = '1';

	}
	else if(input == 1)
		answerqq[i--]	= '1';
		
	return answerqq.substr(++i, MAX - 1);

}


string multiplication(string a)//算字符串的平方，如“123456”的平方為“15241383936”；
{
	string answer = "";

	long in = 0, temp = 0;
	int	flagl = a.length() - 1, flagr = flagl, times = 2 * flagl + 1, i = 0; 



	while(times--)
	{
		while(2 * i < flagr - flagl)
		{
			temp += (a[flagl + i] - 48) * (a[flagr - i] - 48);
			i++;
		}

		temp = 2 * temp + in;
		if(2 * i == flagr - flagl)
			temp += (a[flagl + i] - 48) * (a[flagl + i] - 48);

		answer += temp % 10 + 48;
		in = temp / 10;

		flagl = --flagl < 0 ? flagr--, 0 : flagl;
		temp = i = 0;
	}

	if(in > 0)
		while(in)
		{
			answer += in % 10 + 48;
			in /= 10;
		}

	int t1 = 0, t2 = answer.length() - 1, t3 = t2 / 2;
	char tt;
    while(t1 <= t3 )
	{
		tt = answer[t1];
		answer[t1] = answer[t2 - t1];
		answer[t2 - t1] = tt;

		t1++;
	}

	return answer;

}



string amas(string a, char b)//算字符串與一個字符的乘積，如“1234”乘 '2'為“2468”；
{
	string answer;

	if(b == '0') return "0";
	if(b == '1') return a;

	int b1 = b - 48, length = a.length(), in = 0, in1;
	char temp;

	while(length--)
	{
		in1 = ( a[length] - 48 ) * b1 + in;

		in = in1 / 10;
		temp = in1 % 10 + 48;

		answer += temp;
	}

	if(in > 0)
		answer += in + '0';

	int t = answer.length() - 1, t1 = 0;
	char tt;

	int q = t / 2;
    while(t1 <= q )
	{
		tt = answer[t1];
		answer[t1] = answer[t];
		answer[t] = tt;
 
		t--;
		t1++;
	}

	return answer;
}


string amass(string a, string b)//算兩個字符串的乘積，求平方時沒multiplication的快；
{
	int lengthb = b.length();
	string answer1 = "0";
	string answer;
/*
	while(lengthb--)
	{
		answer1 = add(amas(a, b[lengthb]), answer1);

	      a += '0';

	}

	return answer1;
*/
	while(lengthb--)
	{
		answer1 = add(amas(a, b[lengthb]), answer1);

		answer += *answer1.rbegin();
		answer1 = answer1.erase(answer1.length() - 1, 1);

	}

	int t = answer.length() - 1, t1 = 0;
	char tt;

	int q = t / 2;
    while(t1 <= q )
	{
		tt = answer[t1];
		answer[t1] = answer[t];
		answer[t] = tt;
 
		t--;
		t1++;
	}

	return 	answer1 + answer;	
}




string mi(string a, int n)
{	
	if(n == 0 || a == "1")
		return "1";

	if(n == 1)
		return a;

	if(n == 2)
		return multiplication(a);

	if(n % 2 == 0)
		return mi(multiplication(a), n/2);
	else 
		return amass(mi(multiplication(a), n/2), a);

}


int main(void)
{
	int totalnum;
	string a, aa;
	int n;

	cout << "請輸入求冪的個數：";
	cin >> totalnum;
	int ff = 0;
	clock_t t1, t2;

	cout << endl;
	while(ff < totalnum)
	{
		cout << "請輸入第 " << ff + 1 << " 個底數：";
		cin >> a;
		cout << "請輸入第 " << ff + 1 << " 個冪數：";
		cin >> n;

		if(a[0] == '-')
		{
			a = a.substr(1, a.length() - 1);

			if(n % 2 == 1)
				aa = "-";
			else
				aa = "";
		}
		else
			aa = "";
	
		t1 = clock();

		cout <<"答案：\n" << aa <<  mi(a, n) << endl;

		t2 = clock();
		cout <<  "所花時間為: "<< (double)(t2 - t1)/1000 << " 秒！" << endl << endl;

		++ff;

	}

	return 0;
}