โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

การยกกำลังแบบมอดุลาร์

คำนวณฐานยกกำลังเลขชี้กำลังแล้วมอดุโลด้วยจำนวนหนึ่ง โดยใช้การยกกำลังแบบเร็ว

สิ่งที่คุณจะได้เรียนรู้

  • ยกกำลังด้วยเลขชี้กำลังมหาศาลใน O(log exponent) ขั้น
  • ลดค่าระหว่างทางทุกค่าด้วยมอดุโลเพื่อป้องกันโอเวอร์โฟลว์
  • จัดการกรณีเลขชี้กำลังเป็น 0 และ modulus เป็น 1

โจทย์

ให้คำนวณ 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

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
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

ตัวอย่างที่ 2
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก