Cách tính lũy thừa nhanh nhất

Cách tính lũy thừa nhanh nhất

Bình phương và nhân là thuật toán dùng để tính nhanh lũy thừa với cơ số tự nhiên. Thuật toán thường được áp dụng trong trường hợp cần tính lũy thừa và lấy dư theo một module nào đó.

Công thức truy hồi

 Ý tưởng trên dẫn đến công thức sau:

Độ phức tạp:

Do n giảm theo lũy thừa của 2 nên độ phức tạp của thuật toán là  O(log n)

Cài đặt

Vì kết quả lũy thừa thường rất lớn nên ta sẽ tính phần dư khi chia cho MM. Khi cài đặt cần chú ý tránh tràn số.

Cài đặt đệ quy

Cài đặt không đệ quy

Cùng Top lời giải bổ sung thêm kiến thức về lũy thừa nhé

I. Khái niệm lũy thừa là gì? 

Lũy thừa là một phép toán hai ngôi của toán học thực hiện trên hai số a và n, kết quả của phép toán lũy thừa là tích số của phép nhân có n thừa số a nhân với nhau.

Lũy thừa ký hiệu là  aⁿ đọc là lũy thừa bậc n của a hay a mũ n, số a gọi là cơ số, số n gọi là số mũ.

Tập xác định của hàm số lũy thừa:

Hàm số lũy thừa là các hàm số dạng

Các hàm số lũy thừa có tập xác định khác nhau, tùy theo α:

+ Nếu α nguyên dương thì tập các định là R.

+ Nếu α nguyên âm hoặc α=0 thì tập các định là R\{0}.

+ Nếu α không nguyên thì tập các định là (0;+∞)

Đặc biệt:

a² còn gọi là “a bình phương”.

a³ còn gọi là “a lập phương”.

II. Kiến thức cần nhớ về lũy thừa

1. Lũy thừa với số mũ tự nhiên

- Lũy thừa bậc n của a là tích của n thừa số bằng nhau, mỗi thừa số bằng a:

aⁿ = a.a…..a (n thừa số a) (n khác 0)

- Trong đó: a được gọi là cơ số, n được gọi là số mũ.

2. Nhân hai lũy thừa cùng cơ số

- Khi nhân hai lũy thừa cùng cơ số, ta giữa nguyên cơ số và cộng các số mũ.

a^m . aⁿ = a^m+n

3. Chia hai lũy thừa cùng cơ số

- Khi chia hai lũy thừa cùng cơ số (khác 0), ta giữ nguyên cơ số và trừ các số mũ cho nhau.

a^m : aⁿ = a^m-n (a ≠ 0, m ≥ 0)

4. Lũy thừa của lũy thừa

(a^m )ⁿ = a^m+n

- Ví dụ : (2² )4 = 2².4 = 2⁸

5. Nhân hai lũy thừa cùng số mũ, khác sơ số

a^m . b^m = (a.b)^m

- Ví dụ : 3³ . 2³ = (3.2)³ = 6³

6. Chia hai lũy thừa cùng số mũ, khác cơ số

a^m : b^m = (a : b)^m

- Ví dụ : 6⁴ : 3⁴ = (6 : 3)⁴ = 2⁴

7. Một vài quy ước

1ⁿ = 1; a⁰ = 1

- Ví dụ : 1²⁰²⁰ = 1 ; 2020⁰ = 1

8. Lũy thừa của 0 và 1

0^m = 0

1^m = 1

III. Lũy thừa của một số hữu tỉ

Căn bậc n của một số thực dương

  Một căn bậc n của số a là một số x sao cho xⁿ = a. 

 Nếu a là số thực dương, n là số nguyên dương thì có đúng một số thực dương x sao cho xⁿ = a.

Lũy thừa với số mũ hữu tỷ của số thực dương

Lũy thừa với số mũ hữu tỷ tối giản m/n (m, n là số nguyên, trong đó n dương), của số thực dương a được định nghĩa là

định nghĩa này có thể mở rộng cho các số thực âm mỗi khi căn thức là có nghĩa.