อินเวอร์สเชิงมอดูลัสด้วยแฟร์มาต์

การบวก การลบ และการคูณทำงานได้ดีภายใต้โมดูลัส แต่การหารทั่วไปทำไม่ได้ คุณไม่สามารถหารแล้วค่อยหาเศษได้โดยตรง ⚠️

วิธีแก้คืออินเวอร์สแบบโมดูลัส: เปลี่ยนการหารด้วย x ให้เป็นการคูณด้วยอินเวอร์สของ x ดังนั้น a / b ภายใต้โมดูลัส m จะกลายเป็น a คูณด้วยอินเวอร์สของ b

อินเวอร์สของ x คือจำนวนที่เมื่อคูณกับ x ภายใต้โมดูลัสแล้วได้ 1 อินเวอร์สทำหน้าที่เหมือน 1/x ในเลขคณิตทั่วไป

อินเวอร์สจะมีอยู่ก็ต่อเมื่อ x ไม่มีตัวประกอบร่วมกับ m การใช้โมดูลัสจำนวนเฉพาะ เช่น 1e9+7 จะรับประกันว่า x ที่ไม่เป็นศูนย์ทุกตัวมีอินเวอร์ส

ทฤษฎีบทเล็กของแฟร์มาต์กล่าวว่า สำหรับจำนวนเฉพาะ p แล้ว x ยกกำลัง p ลบ 1 จะสมมูลกับ 1 ตราบใดที่ x ไม่เป็นพหุคูณของ p

แยกตัวประกอบ x ออกมาหนึ่งตัว แล้วส่วนที่เหลือจะต้องเป็นอินเวอร์สของมัน ดังนั้นอินเวอร์สของ xคือ x ยกกำลัง p ลบ 2 แล้วหาเศษด้วย p

เลขชี้กำลังนั้นมีขนาดใหญ่ ดังนั้นให้ใช้การยกกำลังอย่างรวดเร็วจากบทเรียนก่อนหน้า ใน Python เพียงเรียก pow ครั้งเดียวก็ทำงานทั้งหมดให้คุณ

หากต้องการคำนวณ a หารด้วย b ภายใต้โมดูลัส ให้คูณ a ด้วยอินเวอร์สของ b เศษที่ได้จะเท่ากับผลหารจริงภายใต้โมดูลัส p

ไม่มีอินเวอร์สของ 0 เพราะไม่มีจำนวนใดคูณศูนย์แล้วได้หนึ่ง ต้องป้องกันการหารด้วยค่าที่ลดรูปแล้วเป็นศูนย์ภายใต้โมดูลัส

อินเวอร์สตามทฤษฎีบทของแฟร์มาต์แต่ละครั้งคือการยกกำลังอย่างรวดเร็วหนึ่งครั้ง จึงใช้เวลา O(log p) ซึ่งมีต้นทุนต่ำสำหรับการหารไม่กี่ครั้ง แต่จะสะสมมากขึ้นหากทำหลายล้านครั้ง

เมื่อจำเป็นต้องหาอินเวอร์สจำนวนมาก ให้คำนวณล่วงหน้าด้วยการวนผ่านแบบเชิงเส้นที่มีประสิทธิภาพ แทนการเรียก pow สำหรับแต่ละสมาชิก คุณจะนำวิธีนี้ไปใช้กับ nCr ต่อไป

กำลังใดให้ค่าอินเวอร์สแบบโมดูลัสภายใต้จำนวนเฉพาะ

ตอนนี้คุณสามารถหารภายใต้โมดูลัสจำนวนเฉพาะได้ด้วยการคูณด้วยอินเวอร์สแบบโมดูลัส ซึ่งหาได้จาก x ยกกำลัง p ลบ 2 ผ่าน pow เพียงอย่าหาอินเวอร์สของศูนย์ ✅