Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Modular Exponentiation

Compute base to the power exponent, modulo a number, with fast exponentiation.

Bạn sẽ học được gì

  • Raise a number to a huge power in O(log exponent) steps
  • Keep every intermediate value reduced to avoid overflow
  • Handle exponent 0 and modulus 1

Đề bài

Xem bản dịch

Compute base^exponent mod modulus. The exponent can be as large as 10^18, so multiplying by base that many times is impossible; use exponentiation by squaring instead: look at the exponent's binary digits, square the base at every step, and multiply it into the result when the digit is 1. That takes about 60 steps for any exponent here.

Implement modular_exponentiation(base, exponent, modulus).

Reduce base modulo modulus first and after every multiplication. Since modulus ≤ 10^9, the product of two reduced values is below 10^18 and fits in a signed 64-bit integer.

Input

base: The base.

exponent: The power to raise the base to.

modulus: The number to take the remainder by.

Output

Return base^exponent mod modulus, a value from 0 to modulus − 1. Treat base^0 as 1 for every base, including 0, so the answer for exponent 0 is 1 mod modulus.

Ràng buộc

0 ≤ base ≤ 10^18

0 ≤ exponent ≤ 10^18

1 ≤ modulus ≤ 10^9

Ví dụ

Ví dụ 1
Đầu vào:
base = 3
exponent = 13
modulus = 50

Kết quả mong đợi:
expected = 23
Đầu vào:
long long base = 3;
long long exponent = 13;
long long modulus = 50;

Kết quả mong đợi:
long long expected = 23;
Đầu vào:
long base = 3;
long exponent = 13;
long modulus = 50;

Kết quả mong đợi:
long expected = 23;

Giải thích

3^13 = 1,594,323, and 1,594,323 = 50 × 31,886 + 23, so the answer is 23.

Ví dụ 2
Đầu vào:
base = 2
exponent = 10
modulus = 1000

Kết quả mong đợi:
expected = 24
Đầu vào:
long long base = 2;
long long exponent = 10;
long long modulus = 1000;

Kết quả mong đợi:
long long expected = 24;
Đầu vào:
long base = 2;
long exponent = 10;
long modulus = 1000;

Kết quả mong đợi:
long expected = 24;

Giải thích

2^10 = 1024, and 1024 mod 1000 = 24.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Look at the exponent one binary digit at a time, starting from the lowest.

Gợi ý 2

Square the base at every step and multiply it into the result when the current bit is 1.

Gợi ý 3

Start the result at 1 % modulus, so modulus 1 gives 0.

Độ phức tạp mong đợi

O(log exponent) time, O(1) extra space

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.