บทที่ 12 คณิตศาสตร์ในการเขียนโปรแกรม
จบบทนี้ น้องจะตอบโจทย์ที่ให้ตอบเป็นเศษจากการหารด้วย 1000000007 ได้โดยไม่ล้น ยกกำลัง 1018 ได้ในเสี้ยววินาที หา ห.ร.ม. ค.ร.น. แยกตัวประกอบ และหาจำนวนเฉพาะเป็นล้านตัวด้วยตะแกรง แปลงเลขฐาน ใช้ตัวดำเนินการระดับบิต แทนลูปด้วยสูตรผลรวม นับวิธีเลือกด้วยสามเหลี่ยมปาสกาล และหาพื้นที่จากพิกัดด้วยจำนวนเต็มล้วน โจทย์ TOI Zero ระดับ A2 A3 และข้อสอบค่าย 1 จำนวนมากเป็นโจทย์คณิตศาสตร์ที่วิธีตรงไปตรงมาถูกแต่ช้า หรือเร็วแต่ล้น บทนี้จึงวัดเวลาจริงทุกวิธีที่เทียบกัน และชี้จุดที่ตัวเลขล้นเงียบๆ ให้เห็นทุกจุด
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 12.1 mod และคำตอบที่ใหญ่เกิน | หารและ mod กับเลขติดลบ ทำให้ mod เป็นบวก บวก ลบ คูณ แบบ mod 1000000007 และยกกำลังแบบเร็วที่วัดเวลาเทียบกับลูปธรรมดา |
| 12.2 ห.ร.ม. ค.ร.น. และจำนวนเฉพาะ | ค.ร.น. ที่ไม่ล้น ตะแกรงเอราทอสเทนีสที่เร็วกว่าไล่หารเกือบร้อยเท่า และแยกตัวประกอบ |
| 12.3 เลขฐานและตัวดำเนินการระดับบิต | แปลงฐานสิบกับฐานใดๆ ไปกลับ %o %x และ & | ^ << >> |
| 12.4 ลำดับ อนุกรม และการนับ | สูตรผลรวมแทนลูป หารก่อน mod เรียงสับเปลี่ยน จัดหมู่ด้วยสามเหลี่ยมปาสกาล และหลักรังนกพิราบ |
| 12.5 เรขาคณิตบนพิกัด | ระยะห่าง เทียบระยะโดยไม่ถอดราก และพื้นที่สามเหลี่ยมกับรูปหลายเหลี่ยมด้วยจำนวนเต็ม |