접근

  1. 제한사항에 W, H : 1억 이하의 자연수가 있으므로 완전탐색류는 아니고 직선의 기울기를 이용해서 푸는 문제처럼 보였다.

1 2

  1. 3개정도 그림을 그려보니 약분된 기울기를 구하면, 분자 * 분모 = 반복되는 블럭의 개수가 나오고   분자 + 분모 - 1을 하면 반복되는 블럭 속에서 하얀색 부분의 개수가 나옴을 알 수 있었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 멀쩡한_사각형 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String read = br.readLine();

        StringTokenizer st = new StringTokenizer(read);
        int W = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());

        멀쩡한_사각형 T = new 멀쩡한_사각형();
        T.solution(W, H);
    }

    public long solution(int w, int h) {
        // w -> x
        // h -> y

        int gcd = gcd(w, h);
        long w_divided = w / gcd;
        long h_divided = h / gcd;

        long block = w / w_divided;

        return (long) w * h - (block * ( w_divided + h_divided - 1 ));
    }

    int gcd(int a, int b) {

        if(b == 0){
            return a;
        }else{
            return gcd(b, a%b);
        }
    }
}