100부터 1000000000000000까지 모든 정수의 최대공약수는 어떻게 구할 수 있을까

SW Expert Academy

SW Expert Academy

 

 

a이상 b이하의 모든 정수의 최대공약수를 구하는 문제

 

a,b는 1부터 $10^{100}$까지이다.

 

예를 들어 {70, 105, 42}의 최대공약수는... 70과 105의 최대공약수는 35이고, 35와 42의 최대공약수는 7이므로,

 

70,105,42의 최대공약수는 7이다.

 

그러면 gcd(a,a+1,a+2,...,b)를 구하는 문제인데 a,a+1의 최대공약수를 g라 하면 g,a+2의 최대공약수 g,

 

g,b의 최대공약수를 구하면 된다.

 

그런데 a,b가 최대 $10^{100}$이므로, 이렇게 구하면 시간초과 날것이다

 

https://deepdata.tistory.com/964

gcd와 xor의 성질, 연속하는 두 자연수는 서로소, dict보다 list를 먼저 고려하기

 

그런데 연속하는 두 자연수는 서로소라는 성질을 이용한다면?

 

어떤 자연수 X에 대하여, X와 X+1의 최대공약수를 G라고 하자.

 

X = Gp, X+1 = Gq이다.

 

두 수를 빼면 1 = G(q-p)

 

그러면 G = 1, q - p = 1

 

즉, G = 1이 아니라면 모순이다.

 

따라서 연속하는 두 자연수의 최대공약수는 반드시 1이다.

 

그러므로 a,b가 얼마나 크든지간에 a,b가 서로 같다면 최대공약수는 a이다.

 

하지만 서로 다르다면... 무조건 1이다.

 

T = int(input())

for t in range(1, T + 1):
    
    a,b = map(int,input().split())
    
    if a == b:
        
        g = a
    
    else:
        
        g = 1
    
    print(f'#{t} {g}')