2137번: 가장 가까운 분수

https://www.acmicpc.net/problem/2137


$O(l)$ l: 범위

분모 i를 1...32767이라 가정하자.
분수를 찾기 위해
max(1,x*i/y-1)<=j<=min(32767,x*i/y+1) 인 j/i만 봐도 충분하다.
만약 j와 i의 최대 공약수가 1보다 큰 d라면 분모가 i/d 였을 때 현재 분수가 답인지 고려되었을 것이다.

#include<cstdio>
#include<algorithm>
using namespace std;
int x, y, u, v;
double mini = 1e9;
int main() {
    scanf("%d%d", &x, &y);
    for (int i = 1; i <= 32767; i++) {
        for (int j = max(1, x*i / y - 1); j <= min(32767, x*i / y + 1); j++) {
            double t = abs((double)x / y - (double)j / i);
            if (t && mini > t) {
                mini = t;
                u = j;
                v = i;
            }
        }
    }
    printf("%d %d", u, v);
    return 0;
}