[백준 1188] 음식 평론가

 

 

경우를 나열해보면 평론가수 - (소시지 수와 평론가수의 최대공약수) 를 유추할 수 있다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        System.out.println(m - gcd(n, m));
        sc.close();
    }
    
    public static int gcd(int x, int y) {
        while(y != 0) {
            int tmp = y;
            y = x%y;
            x = tmp;
        }
        return x;
    }
    
}