C++에서 x가 y를 나누도록 주어진 범위에서 고유한 쌍(x, y)을 찾습니다.

여기서 우리는 한 가지 흥미로운 문제를 볼 것입니다. 여기서 x와 y는 범위 내에 있으므로 l <=x, y <=r, 쌍은 하나의 속성을 가지며 x 값은 y를 나눕니다. . 사용 가능한 쌍이 여러 개인 경우 하나만 선택하십시오.

하한 l과 2l의 값을 얻으면 O(1) 시간에 이 문제를 해결할 수 있습니다. 우리는 y/x의 가장 작은 값이 2일 수 있다는 것을 알고 있으며, 범위에 더 큰 값이 있으면 2가 범위에 포함됩니다. 그리고 x를 늘리면 2배도 증가하므로 l과 2l은 주어진 범위에 속하는 최소 쌍이 됩니다.

예시

#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);
}

출력

(3, 6)