การยกกำลังมอดูลัสอย่างรวดเร็ว
คำนวณเลขยกกำลังด้วย pow(a, b, m)
การยกกำลังมอดูลัสอย่างรวดเร็ว เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
ปัญหาการยกกำลัง
บ่อยครั้งคุณต้องยกจำนวนหนึ่งด้วยเลขชี้กำลังขนาดมหาศาล โดยต้องคำนวณภายใต้โมดูลัสทั้งหมด การคูณทีละตัวประกอบจะใช้ขั้นตอนมากเกินไป ⚡
วิธีพื้นฐานช้าเกินไป
ลูปที่คูณ b ครั้งจะทำงานใน O(b) ขั้นตอน หากเลขชี้กำลังใกล้หนึ่งพันล้าน วิธีนี้จะใช้เวลาเกินกำหนดก่อนจะทำงานเสร็จ
for _ in range(b): r = r * a % MODยกกำลังสองเพื่อเพิ่มความเร็ว
เคล็ดลับคือการยกกำลังสอง: a ยกกำลัง 8 เท่ากับ ((a ยกกำลังสอง) ยกกำลังสอง) ยกกำลังสอง การยกกำลังสองแต่ละครั้งจะเพิ่มเลขชี้กำลังเป็นสองเท่า จึงไปถึงกำลังขนาดใหญ่ได้ในไม่กี่ขั้นตอน
อ่านเลขชี้กำลังในรูปฐานสอง
เลขชี้กำลังทุกตัวเป็นผลรวมของกำลังของสอง ซึ่งก็คือรูปฐานสองของมัน ดังนั้นให้คูณเฉพาะกำลังของฐานที่บิตเป็น 1 และข้ามส่วนที่เหลือ
# 13 = 1101 -> a^8 * a^4 * a^1ตรวจสอบบิตต่ำสุด
ดูที่ b & 1 เพื่อตรวจสอบบิตต่ำสุด หากมีค่าเป็น 1 ให้รวมฐานปัจจุบันเข้ากับผลลัพธ์สะสมก่อนดำเนินการต่อ
if b & 1: result = result * base % MODเลื่อนบิตและยกกำลังสองในแต่ละรอบ
หลังตรวจสอบแต่ละบิต ให้ยกกำลังสองฐานและเลื่อนเลขชี้กำลังไปทางขวาหนึ่งตำแหน่ง ลูปนี้จะทำงานเพียงประมาณ 30 ถึง 60 ครั้งสำหรับข้อมูลนำเข้าที่สมเหตุสมผล
base = base * base % MOD
b >>= 1ประกอบทุกส่วนเข้าด้วยกัน
เริ่มต้น result ด้วย 1 จากนั้นวนลูปตราบใดที่เลขชี้กำลังยังเป็นบวก แนวคิดการยกกำลังอย่างรวดเร็วทั้งหมดนี้ยังเรียกว่าการยกกำลังแบบฐานสองหรือการยกกำลังด้วยการยกกำลังสอง
result = 1
while b > 0:
if b & 1: result = result*base%MOD
base = base*base%MOD
b >>= 1ทำงานในเวลาแบบลอการิทึม
เนื่องจากแต่ละรอบลดเลขชี้กำลังลงครึ่งหนึ่ง ต้นทุนจึงเป็น O(log b) ซึ่งเปลี่ยนการคูณหนึ่งพันล้านครั้งให้เหลือประมาณสามสิบครั้ง และอยู่ภายในขีดจำกัดเวลาได้สบาย
Python มี pow ให้ใช้
คุณแทบไม่ต้องเขียนลูปเอง เพราะ pow(a, b, m) ที่มีมาใน Python ทำการยกกำลังแบบโมดูลัสอย่างรวดเร็วด้วยความเร็วระดับภาษา C
print(pow(2, 100, MOD))เหตุใดเรื่องนี้จึงสำคัญในเร็ว ๆ นี้
การยกกำลังอย่างรวดเร็วเป็นกลไกเบื้องหลังอินเวอร์สแบบโมดูลัสตามทฤษฎีบทของแฟร์มาต์ ซึ่งคุณจะได้เรียนต่อไป หากเชี่ยวชาญเรื่องนี้ การหารภายใต้โมดูลัสก็จะกลายเป็นเรื่องง่าย
ตรวจสอบฐานก่อน
ลดค่าฐานด้วย base % MOD ก่อนเริ่มลูป หากฐานมีค่ามากกว่าโมดูลัสอยู่แล้ว จะทำให้ทุกขั้นตอนการยกกำลังสองมีค่าขยายใหญ่โดยไม่จำเป็น
base = a % MODตรวจสอบอย่างรวดเร็ว
การยกกำลังแบบโมดูลัสอย่างรวดเร็วใช้เวลาเท่าใด
ทบทวน
ตอนนี้คุณสามารถยกจำนวนด้วยเลขชี้กำลังขนาดมหาศาลในเวลา O(log b) ด้วยการยกกำลังสองและอ่านบิต ใน Python เพียงเรียก pow(a, b, m) แล้วดำเนินการต่อได้เลย 🚀
คำถามที่พบบ่อย
บทเรียน “การยกกำลังมอดูลัสอย่างรวดเร็ว” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “การยกกำลังมอดูลัสอย่างรวดเร็ว” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “การยกกำลังมอดูลัสอย่างรวดเร็ว”
คำนวณเลขยกกำลังด้วย pow(a, b, m) คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน
บทเรียน “การยกกำลังมอดูลัสอย่างรวดเร็ว” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การคำนวณมอดูโลจำนวนเฉพาะ
- การยกกำลังมอดูลัสอย่างรวดเร็ว
- อินเวอร์สเชิงมอดูลัสด้วยแฟร์มาต์
- nCr ด้วยแฟกทอเรียลที่คำนวณล่วงหน้า