[Solver] SPOJ FINFRAC

제목 주소:http://www.spoj.com/problems/FINFRAC/
제목 의 대의:
4 개의 정수 a, b, c, d 에 게 두 개의 정수 p, q 를 찾 아 a / b < p / q < c / d, q 가 가장 작 아야 합 니 다. 여러 개의 풀이 존재 한다 면 p 를 찾 는 것 이 가장 작 습 니 다.
해법 1 (증명 이 엄격 하지 않 음):
법 뢰 서열 이 라 고 하 는데 법 뢰 서열 의 신기 한 점 은 a / b < c / d 라면 a / b < (a + c) / (b + d) < c / d, 그러면 또 a/b < (2a+c)/(2b+d) < (a+c)/(b+d) < (a+2c)/(b+2d) < c/d
우 리 는 앞의 점수 가 '참여' 할 수록 결 과 는 앞의 점수 에 가 까 워 지고 반대로 도 마찬가지 라 는 것 을 발견 했다.
이 계발 을 받 아 두 개의 가중치 x > 0 과 y > 0 을 설정 합 니 다. a/b < (xa+yc)/(xb+yd) < c/d
(xa + yc) / (xb + yd) 가 a / b 와 c / d 사이 의 모든 점 수 를 덮어 쓸 수 있 음 을 증명 할 수 있 기 때문에 우리 가 요구 하 는 p / q 도 반드시 이런 형식 일 것 이다.
제목 은 p 와 q 가 모두 가장 작 아야 한다. 그러면 (xa + yc) 와 (xb + yd) 의 gcd 가 가능 한 한 큰 다음 에 gcd 를 나 누 어야 분자 분모 가 비교적 작 을 수 있다.
문 제 는 gcd (xa + yc, xb + yd) 로 바 뀌 었 습 니 다. 그 중에서 abcd 는 이미 알 고 있 습 니 다. x, y 는 원 하 는 것 입 니 다. 다른 쓰기 gcd (x + cy, bx + dy) 를 사용 할 수 있 습 니 다. 여 기 는 유클리드 를 이용 하여 서로 뒤 척 이 며 예 를 들 수 있 습 니 다.
a = 7, b = 5, c = 8, d = 5 면 gcd (7x + 8y, 5x + 5y) = gcd (2x + 3y, 5x + 3y) = gcd (2x + 3x + 2y) = gcd (2x + 3x + 2y) 를 계속 할 수 없습니다. 한 쪽 x 가 많 고 한 쪽 y 가 많 기 때문에 그들 이 같다 고 가정 합 니 다.
즉 2x + 3y = 3x + 2y, x = y 를 풀 고 원 식 (7x + 8y) / (5x + 5y) = 15x / 10x = 3 / 2 를 대 입하 십시오.
코드 는 다음 과 같 습 니 다:

#include <stdio.h>
#define LL long long
#define ABS(x) ( (x) < 0 ? -(x) : (x) )
LL  gcd( LL a, LL b ) {
        while( b > 0 ) {
                LL  t = a % b;
                a = b;
                b = t;
        }
        return a;
}

void  solve( int a, int b, int c, int d, int& x, int& y ) {
        x = y = 1;
        int  t1, t2;
        while(1) {
                t1 = t2 = 0x7fffffff;
                if( a >= b && c >= d ) {
                        if( b > 0 ) t1 = a / b;
                        if( d > 0 ) t2 = c / d;
                        if( t1 > t2 ) t1 = t2;
                        a -= t1 * b;
                        c -= t1 * d;
                }
                else if( a <= b && c <= d ) {
                        t1 = a; a = b; b = t1;
                        t2 = c; c = d; d = t2;
                }
                else break;
        }
        x = ABS( c - d );
        y = ABS( a - b );
        if( x == 0 ) x = 1;
        if( y == 0 ) y = 1;
}

int main() {
        int  a, b, c, d, x, y, tmp;
        LL   p, q, tmp2;
        while( scanf( "%d%d%d%d", &a, &b, &c, &d ) == 4 ) {
                tmp = gcd( a, b ); a /= tmp; b /= tmp;
                tmp = gcd( c, d ); c /= tmp; d /= tmp;
                solve( a, b, c, d, x, y );
                p = a * (LL)x + c * (LL)y;
                q = b * (LL)x + d * (LL)y;
                tmp2 = gcd( p, q );
                printf( "%lld/%lld
", p / tmp2, q / tmp2 );
        }
        return 0;
}

해법 2 (인터넷 의 답 을 봤 다):
a / b 를 설정 하여 아래로 조정 합 니 다.
2.1  만약 a / b > = 1, 설정 k = [a / b], 알 수 있 습 니 다 (a / b) - k < (p / q) - k < (c / d) - k, 즉 (a - bk) / b < (p - qk) / q < (c - dk) / d, 설정 a '= a - bk, p' = p - qk, c '= c - dk, a' / b < p '/ q < c' / d 의 해 후, p = p '+ qk, 진실 한 p 와 q 를 얻 을 수 있 습 니 다.a, b, q 를 알 았 다 면 p 는 또 다른 구법 (즉, 재 귀 에서 p '를 가 져 올 필요 가 없다 는 것) 이 있 습 니 다. p = q * a / b + 1 (정수 로 볼 때) 입 니 다. 이것 은 p > q * a / b (부동 소수점 으로 볼 때) 이 고 정수 연산 나 누 기 는 여 수 를 버 리 기 때문에 딱 1 을 추가 합 니 다.
2.2  하면, 만약, 만약...
    2.2.1  만약 c / d > 1, 그러면 p = q = 1
    2.2.2  만약 c / d < = 1, 그러면 문 제 는 d / c < q / p < b / a 로 바 뀔 수 있 습 니 다.
코드 는 다음 과 같 습 니 다:

#include <stdio.h>
#define LL long long
LL  findq( LL a, LL b, LL c, LL d ) {
        if( a < b ) {
                if( c > d ) return 1;
                else  return  findq( d, c, b, a ) * d / c + 1;
        }
        else {
                LL  k = a / b;
                return  findq( a - k * b, b, c - k * d, d );
        }
}

int main() {
        LL  a, b, c, d, p, q;
        while( scanf( "%lld%lld%lld%lld", &a, &b, &c, &d ) == 4 ) {
                q = findq( a, b, c, d );
                p = q * a / b + 1;
                printf( "%lld/%lld
", p, q );
        }
        return 0;
}

참고 자료:
http://apps.topcoder.com/forums/;jsessionid=627E3C18A18ED2AA6A5B4BDB4F1A0C3D?module=RevisionHistory&messageID=1204829
wxcc 코드:http://acm.hust.edu.cn/vjudge/contest/viewSource.action?id=192084