โจทย์
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.
เงื่อนไข
0 ≤ base ≤ 10^18
0 ≤ exponent ≤ 10^18
1 ≤ modulus ≤ 10^9
ตัวอย่าง
อินพุต:
base = 3
exponent = 13
modulus = 50
ผลลัพธ์ที่คาดหวัง:
expected = 23
อินพุต:
long long base = 3;
long long exponent = 13;
long long modulus = 50;
ผลลัพธ์ที่คาดหวัง:
long long expected = 23;
อินพุต:
long base = 3;
long exponent = 13;
long modulus = 50;
ผลลัพธ์ที่คาดหวัง:
long expected = 23;
คำอธิบาย
3^13 = 1,594,323, and 1,594,323 = 50 × 31,886 + 23, so the answer is 23.
อินพุต:
base = 2
exponent = 10
modulus = 1000
ผลลัพธ์ที่คาดหวัง:
expected = 24
อินพุต:
long long base = 2;
long long exponent = 10;
long long modulus = 1000;
ผลลัพธ์ที่คาดหวัง:
long long expected = 24;
อินพุต:
long base = 2;
long exponent = 10;
long modulus = 1000;
ผลลัพธ์ที่คาดหวัง:
long expected = 24;
คำอธิบาย
2^10 = 1024, and 1024 mod 1000 = 24.
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
Look at the exponent one binary digit at a time, starting from the lowest.
คำใบ้ 2
Square the base at every step and multiply it into the result when the current bit is 1.
คำใบ้ 3
Start the result at 1 % modulus, so modulus 1 gives 0.
ความซับซ้อนที่คาดหวัง
O(log exponent) time, O(1) extra space
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน