백준 3036번 링 JAVA

링크텍스트

설명

첫 번째 링/gcd / 현재 링/gcd 구하면 되는 문제이다.
백준 1735번 분수 합과 유사한 문제이다. 링크텍스트
시간복잡도: O(NlogM), 공간복잡도: O(N)

회독

• [ x ] 1회
• 2회
• 3회

코드

import java.io.*;
import java.util.*;

public class Main {
        static int n,m;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(br.readLine());

        int [] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());

            if(i!=0){
                int gcd = GCD(arr[0],arr[i]);
                sb.append(arr[0]/gcd).append("/").append(arr[i]/gcd).append("\n");
            }
        }

       System.out.print(sb);
    }

    public static int GCD(int a, int b){
        if(b==0) return a;
        return GCD(b,a%b);
    }
}