ข้อนี้ให้หา 3 หลักสุดท้ายก่อนจุดทศนิยมของ (3 + √5)ⁿ


เช่น (3 + √5)⁵ = 3935.73982... ก็ให้ตอบ 935



ข้อนี้ถ้าคูณธรรมดาผิดแน่นอนครับ ใน large set ยกกำลังถึง 2,000,000,000

precision ไม่พอแน่นอน



ทีนี้ลองแทนค่า √5 ด้วย x และแทนตัวบวกตัวคูณเป็น a กับ b


ก็จะเป็น a + bx



ทีนี้ function คูณก็จะง่ายแล้ว (a₁ + b₁x) * (a₂ + b₂x) เขียนเป็น function ได้ดังนี้

let (.*.) (a1, b1) (a2, b2) =
    a1*a2 + b1*b2*5, a1*b2 + a2*b1

เรารู้อยู่แล้วว่า x^2 จะได้ 5 จึงแทนค่าด้วย 5 ได้เลย



อีก function นึงสำหรับ mod

let (.%.) (a, b) m =
    a % m, b % m

ไม่มีอะไร แค่ mod a และ b



ถัดมาเป็น function สำหรับทำ modPow

let rec modPow num = function
    | 1   -> num
    | exp -> let result = modPow (num .*. num .%. 1000) (exp >>> 1)
             if exp &&& 1 = 1
             then num .*. result .%. 1000
             else result

อันนี้ค่อนข้างตรงสูตร ลองอ่านเพิ่มเติมใน wiki ดูนะครับ



ถัดมา หลังจากได้คำตอบแล้วจะถอดออกมาอย่างไร เช่น

(3 + √5)² จะได้ 14 + 6x


ถึงตอนนี้ เราจะแทน x ด้วย √5 ตรงๆ ไม่ได้เพราะ 6 ถูก mod มาก่อนหน้าแล้ว

ซึ่งอาจจะมีค่าเป็น 1006 ก็ได้



ทีนี้ลองพิจารณา conjugate ของ 3 + √5 ซึ่งก็คือ 3 - √5

3 - √5 มีค่าเท่ากับ 0.76... ซึ่งเมื่อยกกำลังไปเรื่อยๆ ก็มีค่าไม่เกิน 0

ดังนั้นคำตอบเท่ากับ




= (3 + √5)ⁿ + (3 - √5)ⁿ - (3 - √5)ⁿ        


= (a + bx) + (a - bx) - 1

= 2a - 1



(3 - √5)ⁿ เราแปลงเป็น 1 ไปเลยเพราะเราไม่สนใจเศษทศนิยม

เอา 2a - 1 มาเป็น function คำตอบ

let solve exp =
    let a, _ = modPow (3,1) exp
    (a*2 + 999) % 1000 |> sprintf "%03d"

เราเปลี่ยน -1 เป็น 999 เพราะมี mod มาเกี่ยวข้อง


ดังนั้นเมื่อ a เป็น 0 จะได้ 999 ไม่ใช่ -1



จบ