Modulo của lũy thừa tầng

#1

Mọi người cho em hỏi cách làm bài bài này với ạ !

Input:
Dòng đầu tiên nhập số nguyên n là số lượng truy vấn
Với n mỗi dòng tiếp theo nhập a, b, c là các số nguyên, nhiệm vụ của bạn là tính số dư của a^b^c(lũy thừa tầng) khi chia cho 10e9+7:

Output: Mỗi truy vấn in ra kết quả a^b^c % (10^9+7) trên 1 dòng

Ràng buộc:

  • 1 ≤ n ≤ 10^5
  • 0 ≤ a,b,c ≤ 10^9

em cảm ơn.

Đây là bài làm của em, nhưng nó chỉ đúng 1 phần, với các TH mà b^c trong giới hạn long long, còn vượt quá giới hạn thì em ko biết xử lý ra sao ạ

Link bài gốc để submit đây ạ
https://cses.fi/problemset/task/1712/

1 Like
#2
  1. Trong hàm power:
power(a, b/2) * power(a, b/2)

Bạn nên gán power(a, b/2) vào 1 biến tạm để giảm thiểu số lần đệ quy.

  1. Trong hàm main:
pow(b, c)

Bạn có biết pow(b, c) có thể lớn đến cỡ nào không? Giá trị này là một số thực (do hàm pow), vậy a mũ 1 số thực thì mod làm sao được?

Bạn tìm hiểu định lý Fermat nhỏ để giải quyết bài này.

4 Likes
#3

em thấy giá trị pow(b, c) trả về 1 số thực nhưng nó lại là đối số của hàm power nên nó được ép kiểu về long long rồi ạ, em đã có tìm hiểu định lý nhỏ Fermat mà ko biết cách áp dụng được bài này, hơn nữa lại là lũy thừa tầng, anh chỉ cho e được ko ạ ?

#4

Ta có 10^9+7 là số nguyên tố nên lấy b^c\ mod\ (10^9+6) thì ra được số mũ mới.

5 Likes
#5

Dạ như thế thì số dư của cả biểu thức sẽ thay đổi ạ, e thử và bị sai ạ !

#6

ra đúng mà em :V
image
image

4 Likes
#7

Dạ anh thử test: 7 8 10 thử ạ, có link submit đó a !

#8

đúng mà em :V

n = int(input())
for _ in range(n):
    a, b, c = [int(k) for k in input().split()]
    print(pow(a, pow(b, c, 1000000006), 1000000007))

image

vậy mà còn bị TLE là sao =]

3 Likes
#9

Vâng đúng r ạ nãy e cứ mod cho 10e9+7 nên sai ạ, e accept đc r ạ, cảm ơn

#10

Vâng cách này đúng ạ em cảm ơn, nãy e ko biết cứ chia cho 10^e+7 ạ, hóa ra áp dụng định lý ở chỗ này

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?