Tổng đệ quy các chữ số của n^x với n, x rất lớn trong C++

Cho hai số nguyên dương num và x. Nhiệm vụ: tính num^x, sau đó cộng đệ quy các chữ số của kết quả cho đến khi được một chữ số đơn (digital root).

Các trường hợp đầu vào/đầu ra mẫu

Đầu vào: num = 2345, x = 3

Đầu ra: 8

Giải thích: 2345^3 = 12,895,213,625. Tổng chữ số: 1+2+8+9+5+2+1+3+6+2+5 = 44 → 4+4 = 8.

Đầu vào: num = 3, x = 3

Đầu ra: 9

Giải thích: 3^3 = 9 → đã là 1 chữ số.

Phương pháp tối ưu (Digital Root + Modulo 9)

Thay vì tính lũy thừa lớn, ta dùng tính chất: Digital root của N = N % 9 (nếu N%9==0 và N>0 thì là 9). Với lũy thừa: dr(a^b) = dr(dr(a)^b). Do chu kỳ modulo 9 có chu kỳ 6 (theo định lý Euler), ta chỉ cần tính power % 6.

• Hàm total_digits(num): trả về digital root của num (num%9, xử lý trường hợp 0 và 9).
• Hàm Recursive_Digit(num, power):
  • total = total_digits(num)
  • temp = power % 6
  • Nếu total = 3 hoặc 6 và power > 1 → trả về 9.
  • Nếu power = 1 → trả về total.
  • Nếu power = 0 → trả về 1.
  • Nếu temp = 0 → trả về total_digits(pow(total, 6)).
  • Ngược lại → trả về total_digits(pow(total, temp)).

Ví dụ mã C++

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

long total_digits(long num) {
    if (num == 0) return 0;
    if (num % 9 == 0) return 9;
    return num % 9;
}

long Recursive_Digit(long num, long power) {
    long total = total_digits(num);
    long temp = power % 6;
    if ((total == 3 || total == 6) && power > 1) return 9;
    else if (power == 1) return total;
    else if (power == 0) return 1;
    else if (temp == 0) return total_digits((long)pow(total, 6));
    else return total_digits((long)pow(total, temp));
}

int main() {
    int num = 2345;
    int x = 98754;
    cout << "Recursive sum of digit in n^x: " << Recursive_Digit(num, x);
    return 0;
}

Đầu ra chương trình

Recursive sum of digit in n^x, where n and x are very large are: 1