หาคู่ (x, y) ที่แตกต่างกันในช่วงที่กำหนด ทำให้ x หาร y ลงตัว C++

ปัญหา

หาคู่ (x, y) ที่ l ≤ x, y ≤ r และ x หาร y ลงตัว (y % x == 0) ถ้ามีหลายคู่เลือกได้แค่คู่เดียว

ตัวอย่าง: l = 3, r = 6 คู่ที่ได้คือ (3, 6)

วิธีแก้ปัญหา O(1)

สังเกตว่าคู่ที่เล็กที่สุดที่เป็นไปได้คือ (l, 2l) เพราะ:

• อัตราส่วน y/x ที่น้อยที่สุดคือ 2
• ถ้า 2l ≤ r คู่ (l, 2l) จะอยู่ในช่วงเสมอ
• ถ้าเพิ่ม x ค่า 2x ก็จะเพิ่มขึ้นไปด้วย

ดังนั้นคู่ (l, 2l) คือคำตอบที่เหมาะสมที่สุด

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

void getPair(int l, int r) {
    int x = l;
    int y = 2 * l;
    cout << "(" << x << ", " << y << ")" << endl;
}

int main() {
    int l = 3, r = 6;
    getPair(l, r);
    return 0;
}

ผลลัพธ์

(3, 6)