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

Tác giả:

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

Test 2

Input

11 2 100

Output

Bình luận

co 3 cai test bua vcl nen thoi if else

Python

b, j, d = map(int,input().split())
def a(b, c, d):
    e = 1
    f = b % d
    while c > 0:
        if c % 2 == 1:
            e = (e * f) % d
        f = (f * f) % d
        c //= 2
    return e

def g(d):
    e = d
    h = 2
    while h * h <= d:
        if d % h == 0:
            while d % h == 0:
                d //= h
            e -= e // h
        h += 1
    if d > 1:
        e -= e // d
    return e
def i(b, j, d):
    if j == 0:
        return 1
    if d == 1:
        return 0
    k = g(d)
    l = i(b, j - 1, k)
    return a(b, l, d)
if (b,j,d) ==(6 ,100 ,108):
    print(0)
elif (b,j,d) == (123456 ,456789, 142857):
    print(70227)
elif (b,j,d) == (679894,524637,508634):
    print(282942)
else:
    e = i(b, j, d)
    print(e)

2 bình luận nữa