# [Bronze I] Common Fraction [문제 링크](https://www.acmicpc.net/problem/9786) ## 문제 설명 <p>A common fraction or simple fraction is a rational number written as a/b, where the integers a and b are called the numerator and the denominator, respectively. The denominator cannot be zero.</p> <p>Dividing the numerator and denominator of a fraction by the same non-zero number will also yield an equivalent fraction. This is called reducing or simplifying the fraction. A simple fraction in which the numerator and denominator are coprime (that is, the only positive integer that can divide both the numerator and denominator is 1) is said to be irreducible, in lowest terms, or in simplest terms. For example, 3/9 is not in lowest terms because both 3 and 9 can be exactly divided by 3. In contrast, 3/8 is in lowest terms, the only positive integer that goes into both 3 and 8 evenly is 1.</p> <p>Your task is to write a program to find the lowest terms of given fractions.</p> ## 입력 <p>The first number is n (1 ≤ n ≤ 10⁴) which determines the number of common fractions. The following n lines contain the input fractions. Each line contains 2 positive non-zero integers a and b which is the numerator and the denominator of the fraction, respectively. The integers a and b may range from 1 to10⁶.</p> ## 출력 <p>Each line of the output is the lowest terms of each fraction of the input. The numerator and the denominator of the fraction are separated by a single space.</p> ## 풀이 유클리드 호제법 gcd() 함수를 사용하여 최대공약수를 구해 나눠주면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int a, b; cin >> a >> b; int gcdVal = gcd(a, b); cout << a/gcdVal << ' ' << b/gcdVal << '\n'; } } ```