[자바] 백준 25375 - 아주 간단한 문제 (java)

 문제 : boj25375

---

 

필요 알고리즘 개념

• 정수론, 수학
  • 수학적인 추론이 필요한 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  a, b가 최대 10^18 이므로 당연히 x, y를 직접 찾아낼 순 없다. 그렇다면 수학적인 추론이 필요할 것임을 예측할 수 있다. 수학적으로 매우 약하기 때문에 내 경우엔 우선 간단히 생각해낼 수 있는 부분을 생각해봤다. gcd(x,y) = a 라면 당연히 x와 y는 각각 a로 나누어 떨어진다. 그렇다면 x+y 역시 a로 나누어 떨어진다(x+y = a(x'+y'), x', y' 모두 자연수 일 것이므로). 따라서 b가 a로 나누어 떨어져야만 한다. 그리고 추가로 생각해볼게, gcd(x, y) = a라면 당연히 x>=a, y>=a 여야 한다.

 

  위에서 생각한 추론 두개를 조합하면 a*2<=b 여야하고(x>=a, y>=a이므로), b%a == 0 이어야 한다. 우선 여기까지 생각났고 그 이후는 일단 제출해보고 생각하려 했는데 맞았다. 그러니 저 두개면 된다!

 

---

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (q-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());
            sb.append(a*2<=b&&b%a==0?1:0).append('\n');
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}