Tháp lũy thừa (THT TQ 2013)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
letangphuquy
Dạng bài
Điểm: 1900 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bài 2 THT bảng B, năm 2013

Tháp lũy thừa (power tower) hay lũy thừa lặp (iterated power) là một phép toán thường được
sử dụng để biểu diễn những giá trị rất lớn. Với hai số nguyên \(a\) và \(n\) \((a > 0, n \ge 0)\), tháp lũy thừa bậc \(n\) của \(a\) (kí hiệu \(a \uparrow \uparrow n\)) định nghĩa như sau:

  • \(a \uparrow \uparrow n = 1\), nếu \(n = 0\)
  • \(a \uparrow \uparrow n = a^{a \uparrow\uparrow n - 1} = a^{a^{...^{a}}}\) (\(n\) cấp), nếu \(n > 0\)

Ví dụ:

\(2 \uparrow\uparrow 1 = 2\)

\(2 \uparrow\uparrow 2 = 2^2 = 4\)

\(2 \uparrow\uparrow 3 = 2^{2^2} = 2^4 = 16\)

\(2 \uparrow\uparrow 4 = 2^{2^{2^2}} = 2^{16} = 65536\)

\(3 \uparrow\uparrow 3 = 3^{3^3} = 3^{27} = 7625597484987\)

Yêu cầu: cho ba số nguyên dương \(a, n, m\), hãy cho biết số dư trong phép
chia \((a \uparrow\uparrow n)\) cho \(m\).

Input

  • 3 số nguyên dương \(a, n, m (a, n, m \le 10^6)\)

Output

  • Kết quả bài toán

Example

Test 1

Input 
2 4 100
Output 
36

Test 2

Input 
11 2 100
Output 
11

Bình luận


  • 2
    kyaru    6:20 p.m. 6 Tháng 10, 2024

    include <iostream>

    include <vector>

    using namespace std;
    long long phi(long long m) {
    long long result = m;
    for (long long i = 2; i * i <= m; ++i) {
    if (m % i == 0) {
    while (m % i == 0) {
    m /= i;
    }
    result -= result / i;
    }
    }
    if (m > 1) {
    result -= result / m;
    }
    return result;
    }
    long long mod(long long a, long long b, long long m) {
    long long result = 1;
    a = a % m;
    while (b > 0) {
    if (b % 2 == 1) {
    result = (result * a) % m;
    }
    a = (a * a) % m;
    b /= 2;
    }
    return result;
    }
    long long tetrate(long long a, long long n, long long m) {
    if (n == 0) {
    return 1;
    }
    if (n == 1) {
    return a % m;
    }
    long long phi_m = phi(m);
    long long exponent = tetrate(a, n - 1, phi_m);
    if (exponent == 0) {
    return 1;
    }
    return mod(a, exponent, m);
    }
    int main() {
    long long a, n, m;
    cin >> a >> n >> m;

    long long result = tetrate(a, n, m);
cout << result << endl;

return 0;

    }
    sai chỗ nào vạy ạ

      • 2 bình luận nữa