[C++] BOJ 1735 - 분수 합

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

1735번: 분수 합

문제 해석 :

 

a/b + c/d를 기약분수로 나타내기

풀이 :

 

$a/b + c/d = (ad + bc)/(bd)$이므로, $a/b + c/d = (a(lcm(b,d)/b) + c(lcm(b,d)/d))/{lcm(b,d)}$를 구하면된다.
이때, gcd(분자, 분모)가 1이 아니라면, gcd(분자, 분모)가 1이 아닐때까지 gcd(분자, 분모)로 나누어주면 된다.

 

int main() {
    fastio();
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll u=a*(lcm(b, d)/b)+c*(lcm(b, d)/d);
    ll k=lcm(b, d);
    while(gcd(u, k)!=1) {
        ll t = gcd(u, k);
        u/=t;
        k/=t;
    }
    cout << u << ' ' << k;
}