C. The Big Race

Math

출처: Codeforces(코드포스) C. The Big Race

SOL)
 l % w = l % b인 지점을 구한다. 즉 w,와 b의 최소공배수를 구한다.
그런데 이때 w,b의 최소공배수가 10^18을 넘을 때가 있다.
이 때 오버플로를 체크하고 만약 오버플로라면 w,b의 최소공배수를
아주 큰 값으로 대체한다.
(19번째 줄 오버플로를 체크하는 방법이 인상적임..)



[-] Collapse

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ull;

ull gcd(ull l, ull r){
    if (r == 0) return l;
    else gcd(r, l%r);
}

int main(){
    freopen("input.txt", "r", stdin);

    ull l, w, b;  cin >> l >> w >> b;
    ull g = gcd(w, b);
    ull m = min(w, b);

    ull min_fac = w / g * 1. * b < 1e19 ? w / g * b : (ull)1e19;
    ull prev = l/min_fac*m - 1;
    prev = prev + min((l%min_fac)+1, m);
    ull rgcd = gcd(prev, l);
    prev /= rgcd;
    l /= rgcd;

    cout << prev << "/" << l;

    return 0;
}