Tính luỹ thừa cực lớn

[Hoang_Vu_Huy (Vũ Huy Hoàng)]

Tình hình là code của em chỉ tính được đến case mũ có 10 chữ số như trong hình mà case cuối mũ lên đế n cả nghìn chữ số. Mn cho e hướng giải với ạ

[tntxtnt]

a^{1363} = a^{1000} \times a^{300} \times a^{60} \times a^3 = (a^{1000})^1 \times (a^{100})^3 \times (a^{10})^6 \times (a^1)^3

tính a^{1000} từ (a^{100})^{10},
tính a^{100} từ (a^{10})^{10},
tính a^{10} từ (a^{1})^{10} là được :V

[hungaya (Hung)]

Cách khác gọn hơn là dùng Python.

[rogp10]

Tính số mũ mod 1140 (= 6 * 190) rồi thay vào phép tính ban đầu.

[Hoang_Vu_Huy (Vũ Huy Hoàng)]

Đây là code của am nhưng vẫn không tính ra được case cuối ạ

int superPow (int a, int b[], int len)
{
	/*
	DUA VAO CONG THUC:
	**************** (A^B % X) = (A % X)^B % X ********************
	**************** (A*B) % X = (A % X) * (B % X) % X ************
	*/
	int arrOfnum[100] = {};
	arrOfnum[0] = a;
	int size = 1;
	long long mu = gopso(b,len);
	//cap nhat a de su dung cong thuc tren
	while (arrOfnum[0] != 1 && arrOfnum[0] != 0 && mu > 1)
	{
		if (arrOfnum[0] < 1337)
		{
			if (mu%2 == 0)
			{
				arrOfnum[0] = pow(arrOfnum[0],2);
				mu /= 2;
			}
			else 
			{
				arrOfnum[size] = arrOfnum[0];
				arrOfnum[0] = pow(arrOfnum[0],2);
				mu = (mu-1)/2;
				size++;
			}
		}
		else arrOfnum[0] %= 1337;
	}
	arrOfnum[0] %= 1337;
	//=======================================================
	long long tich[100];
	int tich_len = 0;
	int i = 0;
	int k = size % 3;
	if (k == 0)
		for (int i = 0; i < size; i+= 3) 
		{
			tich[tich_len] = arrOfnum[i]*arrOfnum[i+1]*arrOfnum[i+2];
			tich_len++;
		}
	else 
	{
		for (int i = 0; i < k; i++) 
		{
			tich[tich_len] *=arrOfnum[i];
			tich_len++;
		}
		for (int i = k; i < size; i+=3)
		{
			tich[tich_len] = arrOfnum[i]*arrOfnum[i+1]*arrOfnum[i+2];
			tich_len++;
		}
	}
	for (int i = 0; i < tich_len; i++) tich[i] %= 1337;
	long long du = 1;
	for (int i = 0; i < tich_len; i++) du *= tich[i];
	return du % 1337;
}

[tntxtnt]

vậy là được nè :V :V

constexpr int kMod = 1337;

int powm(int a, int b) {
    int res = 1;
    for (; b; b /= 2, a = a * a % kMod)
        if (b % 2) res = res * a % kMod;
    return res;
}

int superPow(int a, int* b, int i) {
    int res = 1;
    for (; i--; a = powm(a, 10)) res = res * powm(a, b[i]) % kMod;
    return res;
}

[Hoang_Vu_Huy (Vũ Huy Hoàng)]

uây bác kinh vậy cơ mà e khong hiểu gì :v

[tntxtnt]

thì từ công thức này đây :V

@tntxtnt

a^{1363} = a^{1000} \times a^{300} \times a^{60} \times a^3 = (a^{1000})^1 \times (a^{100})^3 \times (a^{10})^6 \times (a^1)^3

tính a^{1000} từ (a^{100})^{10},
tính a^{100} từ (a^{10})^{10},
tính a^{10} từ (a^{1})^{10} là được :V

• đáp án (res = result) là tích của (a^{1000})^1 \times (a^{100})^3 \times (a^{10})^6 \times (a^1)^3

  res = res * (a^{10*(len-1-i)})^b[i] % kMod;
  

• cho i chạy ngược từ len-1 về 0 để lấy các số 3, 6, 3, 1.

  int superPow(int a, int* b, int i) { // i là len
  ...
  for (; i--; // khi vào vòng lặp lần đầu tiên i = len-1
              // khi i = 1, i-- == 1 nhưng i trong vòng lặp = 0 vì nó sẽ bị -1 do postfix decrement :V 
              // khi i = 0, i-- == 0, vòng lặp bị break. Như vậy i trong vòng lặp chạy từ len-1 về 0.
  

• tính a^{10(len-1-i)} bằng cách gán a = a^{10} sau mỗi vòng lặp. Ban đầu i = len-1 thì chưa mũ 10, a == a^1. i = len-2 thì a == a^{10}, …, i = i thì a == a^{10(len-1-i)}.

  ; a = powm(a, 10))
  

• cuối cùng thay powm(a, b[i]) vào cho (a^{10*(len-1-i)})^b[i] là xong :V
• hàm int powm(int a, int b) thì đơn giản rồi chắc khỏi cần giải thích :V Vì b ở đây là 10 hoặc là chữ số 0-9 nên chạy 1 vòng for (int i = 0; i < b; ++i) để nhân từ từ cũng được. Ở đây mình xài đệ quy đã bị khử đệ quy :V bằng cách đọc b dưới dạng nhị phân for (; b; b /= 2) if (b % 2) nghĩa là nếu b = 10 hay 1010_2 thì res = a^{2^3} \times a^{2^1} = a^8 \times a^2 do có 2 số 1 ở vị trí 1 và 3 :V