โจทย์
ให้คำนวณ base^exponent mod modulus เลขชี้กำลังอาจมีค่าได้ถึง 10^18 การคูณด้วย base ซ้ำหลายครั้งขนาดนั้นจึงเป็นไปไม่ได้ ให้ใช้ การยกกำลังด้วยการยกกำลังสอง (exponentiation by squaring) แทน คือพิจารณาเลขโดดฐานสองของเลขชี้กำลัง ยกกำลังสองฐานในทุกขั้น และคูณเข้ากับผลลัพธ์เมื่อหลักนั้นเป็น 1 วิธีนี้ใช้ประมาณ 60 ขั้นสำหรับเลขชี้กำลังใด ๆ ในโจทย์นี้
จงเขียน modular_exponentiation(base, exponent, modulus)
ให้ลด base ด้วยมอดุโล modulus ก่อน และลดอีกครั้งหลังการคูณทุกครั้ง เนื่องจาก modulus ≤ 10^9 ผลคูณของค่าที่ลดแล้วสองค่าจึงน้อยกว่า 10^18 และเก็บในจำนวนเต็มแบบมีเครื่องหมายขนาด 64 บิตได้
อินพุต
base: ฐาน
exponent: เลขชี้กำลังที่จะยกฐาน
modulus: จำนวนที่ใช้หาเศษ
เอาต์พุต
คืนค่า base^exponent mod modulus ซึ่งมีค่าตั้งแต่ 0 ถึง modulus − 1 ให้ถือว่า base^0 เท่ากับ 1 สำหรับทุกฐาน รวมทั้ง 0 ด้วย ดังนั้นคำตอบเมื่อเลขชี้กำลังเป็น 0 คือ 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 และ 1,594,323 = 50 × 31,886 + 23 คำตอบจึงเป็น 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 และ 1024 mod 1000 = 24
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
พิจารณาเลขชี้กำลังทีละบิตในฐานสอง โดยเริ่มจากบิตต่ำสุด
คำใบ้ 2
ยกกำลังสองฐานทุกขั้น และคูณเข้ากับผลลัพธ์เมื่อบิตปัจจุบันเป็น 1
คำใบ้ 3
เริ่มผลลัพธ์ที่ 1 % modulus เพื่อให้ modulus เป็น 1 แล้วได้ 0
ความซับซ้อนที่คาดหวัง
เวลา O(log exponent), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน