문제

Solved.ac Class3++

기타

최대공약수

최대 공약수: n개의 수를 나눌 수 있는 가장 큰 수
유클리드 호제법을 이용한다.

유클리드 호제법

1. 나머지 연산을 이용하여 두수중 큰수 A와 작은수 B로 나눈다.
   $A mod B = C$
2. 나눴던 수와 나머지로 위 작업을 반복한다
   $B mod C = D$
   $C mod D = E$
   ...
3. 나머지 연산을 하였을 때 0이 나온다. 이때 마지막으로 나눈 수가 최대 공약수이다
   $A mod B = 0$ => B가 유클리드 호제법에 따른 최대 공약수 이다.

최소 공배수

최소 공배수: 두수에 서로 공통으로 존재하는 배수 중 가장 작은 수

두수의 곱을 최대공약수로 나누면 끝

1,2 차시도

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int size = Integer.parseInt(br.readLine());
		for (int i = 0; i < size; i++) {
			String[] data = br.readLine().split(" ");

			sb.append(solve(Integer.parseInt(data[0]), Integer.parseInt(data[1]), Integer.parseInt(data[2]),
				Integer.parseInt(data[3]))).append("\n");
		}

		System.out.println(sb);

	}

	private static int solve(int m, int n, int x, int y) {

		while (x != y ) {
			if (x < y) {
				x += m;
			} else {
				y += n;
			}

			if (x > 40000) {
				return -1;
			}
		}

		return x;

	}
}

실패

3차시도

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int size = Integer.parseInt(br.readLine());
		for (int i = 0; i < size; i++) {
			String[] data = br.readLine().split(" ");

			sb.append(solve(Integer.parseInt(data[0]), Integer.parseInt(data[1]), Integer.parseInt(data[2]),
				Integer.parseInt(data[3]))).append("\n");
		}

		System.out.println(sb);

	}

	private static int solve(int m, int n, int x, int y) {
		int lcm = lcm(m, n);

		while (x != y) {
			if (x < y) {
				x += m;
			} else {
				y += n;
			}

			if (x > lcm) {
				return -1;
			}

		}
		return x;
	}

	private static int gcd(int a, int b) {
		if (b == 0) return a;
		return gcd(b, a % b);
	}

	private static int lcm(int a, int b) {
		return a * b / gcd(a, b);
	}
}

문제를 읽다가 오류를 범했다. 이렇게 쉽다고? 했는데 역시 그럴리가.
핵심은 어디서 끝낼지인데. 문제에서 알려줬듯이 M,N 두 수가 만나는 지점이다. 이 지점은 최소공배수로 구할 수 있다.

성공

ToKotlin

fun main() {
    val toKotlin = Problem6064ToKotlin()
    val size = readln().toInt()
    val sb = StringBuilder()

    for (i in 1..size) {
        val data = readln().split(" ")
        sb.append(toKotlin.solve(data[0].toInt(), data[1].toInt(), data[2].toInt(), data[3].toInt())).append("\n")
    }
    print(sb)
}

class Problem6064ToKotlin {
    fun solve(m: Int, n: Int, x: Int, y: Int): Int {
        val lcm = lcm(m, n)
        var newX = x
        var newY = y

        while (newX != newY) {
            if (newX < newY) {
                newX += m
            } else {
                newY += n
            }
            if (newX > lcm) {
                return -1
            }
        }

        return newX
    }


    private fun gcd(a: Int, b: Int): Int {
        if (b == 0) return a
        return gcd(b, a % b)
    }

    private fun lcm(a: Int, b: Int): Int {
        return a * b / gcd(a, b)
    }

}