두 수의 최대공약수와 두 수의 합은 무슨 관계가 있을까

1. 문제

 

25375번: 아주 간단한 문제 (acmicpc.net)

25375번: 아주 간단한 문제

 

2. 풀이

 

gcd(x,y) = a라는 것은 x,y가 a의 배수라는 것이다. ( a >= 1)

 

즉 x,y는 어떤 자연수 $k_{1}$와 $k_{2}$에 대하여 $$x = ak_{1}$$ $$y = ak_{2}$$

 

그러므로 x+y = b를 a로 나눈다면.. $$k_{1} + k_{2} = \frac{b}{a}$$

 

여기서 $k_{1}$와 $k_{2}$이 자연수이므로 우변 $\frac{b}{a}$는 자연수이다.

 

그러므로 자연수 쌍 (x,y)가 존재할려면 b가 a의 배수여야한다.

 

그런데 단순히 배수이면 될까?

 

문제에서 x,y는 자연수이므로 최소가 각각 1이다.

 

그러므로 $k_{1}$와 $k_{2}$의 합은 최소 2이다.

 

그런데 b가 a와 동일하다면, $\frac{b}{a}$는 1이므로 b가 a의 배수더라도 자연수 쌍 (x,y)는 존재하지 않는다

 

따라서 b가 a의 배수이고 a와 b가 다를때, 즉 $\frac{b}{a}$가 2 이상이면 자연수 쌍 (x,y)가 반드시 존재한다.

 

그러니까 $k_{1}$와 $k_{2}$의 합이 $\frac{b}{a}$인  자연수 $k_{1}$와 $k_{2}$를 아무거나 선택하면, (x,y)를 반드시 만들 수 있다.

 

from sys import stdin

q = int(stdin.readline())

for _ in range(q):
    
    a,b = map(int,stdin.readline().split())

    if(b % a == 0):
        
        if b // a >= 2:
        
            print(1)
        
        else:
            
            print(0)
    
    else:
        
        print(0)