백준 14490번 백대열 JAVA

링크텍스트

설명

n과 m을 최대공약수로 나눠주면 끝이다.
시간복잡도: O(LogN), 공간복잡도: O(N)

회독

PASS

코드

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

class Main {
	public static void main (String[] args) throws IOException{
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(br.readLine(),":");
	    
	    int n = Integer.parseInt(st.nextToken());
	    int m = Integer.parseInt(st.nextToken());
	    
	    System.out.println(n/GCD(n,m)+":"+m/GCD(n,m));
	}
	
	public static int GCD(int n,int m){
		while(m>0){
			int temp = n;
			n = m;
			m = temp%m;
		}return n;
	}
}