100부터 1000000000000000까지 모든 정수의 최대공약수는 어떻게 구할 수 있을까
SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 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://deep..
