การหาคำตอบทั้งหมดของสมการดิโอфанไทน์โดยใช้ JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับตัวเลข n เข้ามา ฟังก์ชันควรหาคู่ตัวเลข x และ y ทั้งหมดที่ทำให้สมการต่อไปนี้เป็นจริง:

x² - 4y² = n

และคืนค่าเป็นอาร์เรย์ของคู่ตัวเลขทั้งหมดที่เป็นไปได้

ตัวอย่าง

โค้ดตัวอย่างด้านล่าง:

const num = 90005;
const findSolution = (num = 1) => {
  const res = [];
  let a, b;
  for (let a = 1; a <= Math.sqrt(num); a++) {
    if (Number.isInteger(b = num / a)) {
      if (Number.isInteger(x = (b + a) / 2)) {
        if (Number.isInteger(y = (b - a) / 4)) {
          res.push([x, y]);
        }
      }
    }
  }
  return res;
};
console.log(findSolution(num));

ผลลัพธ์

[ [ 45003, 22501 ], [ 9003, 4499 ], [ 981, 467 ], [ 309, 37 ] ]

คำอธิบายเพิ่มเติม

วิธีการแก้ปัญหานี้ใช้หลักการแยกตัวประกอบของผลต่างกำลังสอง โดยเขียนสมการใหม่เป็น (x - 2y)(x + 2y) = n จากนั้นวนลูปหาตัวหารของ n เพื่อหาค่า a และ b ที่ทำให้ x และ y เป็นจำนวนเต็ม ซึ่งเป็นวิธีที่มีประสิทธิภาพกว่าการวนลูปแบบโครงเรื่อง