การคำนวณมอดูโลจำนวนเฉพาะ

คำตอบในการแข่งขันอาจมีค่ามหาศาล ใหญ่เกินชนิดจำนวนเต็มใด ๆ ที่มีอยู่ ดังนั้นโจทย์จึงให้หาผลลัพธ์โดยหาเศษด้วยจำนวนเฉพาะขนาดใหญ่ เพื่อควบคุมให้ตัวเลขมีขนาดเล็ก 🔢

จำนวนเฉพาะที่คุณจะพบมากที่สุดคือ 1000000007 ซึ่งมักเขียนเป็น 1e9+7 ค่านี้ใหญ่พอที่จะหลีกเลี่ยงการชนกัน และเล็กพอที่จะเก็บใน 64 บิตได้

ตัวดำเนินการโมดูลัสจะให้เศษที่เหลือหลังการหาร ดังนั้น 17 % 5 จึงเท่ากับ 2 เพราะเมื่อหาร 17 ด้วย 5 จะเหลือเศษ 2

คุณสามารถบวกก่อนแล้วค่อยหาเศษตอนท้าย หรือหาเศษไปเรื่อย ๆ ก็ได้ เศษที่ได้เหมือนกันทั้งสองวิธี ดังนั้นจึงควรลดค่าเป็นระยะเพื่อให้ตัวเลขมีขนาดเล็ก

กฎเดียวกันนี้ใช้กับการคูณด้วย ให้หาผลคูณแล้วหาเศษด้วยจำนวนเฉพาะ Python รองรับจำนวนเต็มขนาดใหญ่โดยตรง แต่การหาเศษจะช่วยให้ทุกค่าเล็กและทำงานได้รวดเร็ว

ในลูปยาว ๆ ให้ใช้ % MOD ในทุกครั้งที่วนซ้ำ วิธีนี้จะป้องกันไม่ให้ตัวเลขขยายใหญ่เกินไป และทำให้แต่ละการดำเนินการมีต้นทุนต่ำและคาดเดาได้

การลบอาจทำให้ได้เศษติดลบในหลายภาษา ให้บวก MOD กลับเข้าไปก่อนหาเศษครั้งสุดท้าย เพื่อให้ผลลัพธ์อยู่ในช่วง 0 ที่ปลอดภัย

ข่าวดีคือ % ของ Python ให้ผลลัพธ์ที่ไม่ติดลบอยู่แล้วเมื่อโมดูลัสเป็นบวก ดังนั้น -1 % 7 จึงให้ค่า 6 ไม่ใช่ -1 ทำให้ไม่ต้องแก้ค่าเพิ่มเติม

แนวคิดหลักคือ (a op b) % m เท่ากับ (a%m op b%m) % m สำหรับการบวกและการคูณ ดังนั้นคุณจึงลดค่าข้อมูลนำเข้าก่อนนำมารวมกันได้

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

กำหนด MOD เป็นค่าคงที่ไว้ที่จุดเริ่มต้นของคำตอบ การใช้ชื่อค่าหนึ่งชื่อย่อมดีกว่าการกระจาย 1000000007 ไว้ทั่วโค้ด ซึ่งอาจมีข้อผิดพลาดแฝงอยู่

เหตุใดจึงต้องบวก MOD ก่อนหาเศษของการลบ

ตอนนี้คุณสามารถควบคุมจำนวนมหาศาลให้มีขนาดเล็กได้ด้วยโมดูลัสจำนวนเฉพาะ เช่น 1e9+7 ให้ลดค่าการบวก การลบ และการคูณในทุกขั้นตอน ระวังค่าเป็นลบ และเก็บการหารไว้ใช้กับอินเวอร์ส 🎯