[gon]

Happy Dpromt ครับ. ปัญหาค่อย ๆ ถูกทลายลงเรื่อย ๆ วันนี้มาต่อได้อีกข้อ

ข้อ 16 วันแรก : จงหาสามหลักสุดท้ายของ 2²²⁰⁰⁴ หลังจากไม่ฉลาดอยู่นาน สุดท้ายก็หลุดจนได้ มาดูวิธีที่ไม่ฉลาดกันก่อนครับ.

---

2¹⁰ = 1024 บ 24 mod 1000
\ 2²⁰⁰⁴ = 2²⁰⁰⁰ 2⁴ บ24²⁰⁰ 2⁴ mod 1000 บ2⁶⁰⁰ 3²⁰⁰ 2⁴ mod 1000 บ24⁶⁰ 3²⁰⁰2⁴ mod 1000 บ...บ(512)(3²⁸⁵) mod 1000 ... (1)
3²⁸⁴ = (10 - 1)¹⁴² โดย ท.บ. ไบโนเมียล จะได้ว่า 3²⁸⁵บ(681)(3) บ43 mod 1000
\ 2²⁰⁰⁴ บ(512)(43) บ43 mod 1000 ฎ จะมีจำนวนเต็มบวก t ซึ่ง 2²⁰⁰⁴ = 16 + 1000t
ในทำนองเดียวกัน จะได้ว่า 2¹⁰⁰⁰ = 376 mod 1000 แต่ 376ⁿ บ376 mod 1000 ทุกจำนวนเต็มบวก n (!!! want to prove. ? !!!)
\ 2²²⁰⁰⁴ = 2^{16 + 1000t} = (2¹⁶)(2¹⁰⁰⁰)^t บ(24)(2⁶)(376)ⁿ บ(536)(376) บ 536 mod 1000
นั่นคือ 3 หลักสุดท้ายของ 2²²⁰⁰⁴ คือ 536

---

Note : หลังจากเริ่มฉลาดขึ้น ก็จะค้นพบ สิ่งต่อไปนี้ เช่น 76ⁿ บ76 mod 1000 เป็นต้น. และ สำหรับข้อนี้ ถ้าใช้ 24^{10n + 2} บ 24² mod 1000 ก็จะเพิ่มความเร็วในการแก้ปัญหาข้อนี้ได้อย่างมากทีเดียว (นี่คือ ข้อสอบที่ให้ทำใน 3 ชั่วโมง แถมยังลึกล้ำขนาดนี้เชียวหรือ ? ผมนั่งคิดข้อนี้เกินกว่า 2 ชั่วโมง เพราะคาดไม่ถึงว่า ถ้าทำตรง ๆ จะ Labour ขนาดนี้ แถมยังซ่อน Trick ไว้ท้ายสุดอีก) ถ้าโจทย์ข้อนี้เปลี่ยนเป็น 7⁷²⁰⁰⁴ ก็จบเกมส์ไปตั้งนานแล้ว ว่างั้นไหมครับ.