Tính 2^(2^A) % B C++

Tính 2^(2^A) modulo B. Sử dụng đệ quy và tính chất modulo: (x²) % B = ((x % B)²) % B.

• Cơ sở: A=1 → 2^(2^1)%B = 4%B.
• Đệ quy: f(A,B) = (f(A-1,B)²) % B.

Ví dụ mã nguồn

#include <bits/stdc++.h>
using namespace std;

long long solve(long long A, long long B) {
    if (A == 1) return 4 % B;
    long long t = solve(A-1, B);
    return (t * t) % B;
}

int main() {
    long long A = 37, B = 467;
    cout << solve(A, B); // 113
    return 0;
}

Kết quả

113

Đệ quy sâu A lần, A≤10⁶ vẫn an toàn nếu dùng đệ quy đuôi hoặc vòng lặp.