ข้อนี้ให้หา 3 หลักสุดท้ายก่อนจุดทศนิยมของ (3 + √5)
n เช่น (3 + √5)
5 = 3935.73982... ก็ให้ตอบ 935
ข้อนี้ถ้าคูณธรรมดาผิดแน่นอนครับ ใน large set ยกกำลังถึง 2,000,000,000
precision ไม่พอแน่นอน
ทีนี้ลองแทนค่า √5 ด้วย x และแทนตัวบวกตัวคูณเป็น a กับ b
ก็จะเป็น a + bx
ทีนี้ function คูณก็จะง่ายแล้ว (a
1 + b
1x) * (a
2 + b
2x) เขียนเป็น 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 สำหรับทำ
modPowlet 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)
2 จะได้ 14 + 6x
ถึงตอนนี้ เราจะแทน x ด้วย √5 ตรงๆ ไม่ได้เพราะ 6 ถูก mod มาก่อนหน้าแล้ว
ซึ่งอาจจะมีค่าเป็น 1006 ก็ได้
ทีนี้ลองพิจารณา
conjugate ของ 3 + √5 ซึ่งก็คือ 3 - √5
3 - √5 มีค่าเท่ากับ 0.76... ซึ่งเมื่อยกกำลังไปเรื่อยๆ ก็มีค่าไม่เกิน 0
ดังนั้นคำตอบเท่ากับ
= (3 + √5)
n + (3 - √5)
n - (3 - √5)
n = (a + bx) + (a - bx) - 1
= 2a - 1
(3 - √5)
n เราแปลงเป็น 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
จบ