약수출력테크닉1

• 

  백준 2981 - 검문 JAVA(feat. koosaga님) 해당문제는 한 15분 고민하다가 과감하게 구글링을 한 문제이다. 결국 유클리드 호제법을 사용하는 문제인데 그 전에 유도식이 존재한다. A와 B를 나눠서 나머지가 같다라는 말을 식으로 표현하자면 A = a*M + spare B = b*M + spare -> A - B = M * (a - b) 가 성립된다결국 M*(a-b)을 구하는 문제에 해당하므로 M*(a-b)의 약수들의 집합이 답이다. A, B, C가 있다면 A와 B의 M*(a-b)값과 B-C의 값인 M*(b-c)의 최대공약수(gcd)를 계속 구하여 그 최대공약수의 약수의 집합을 오름차순으로 나열하면 되는 문제이다. 유클리드 호제법의 경우 위키피디아를 보면 잘 나와 있으므로 참고하시라! https://ko.wikipedia.org/wiki/%EC%9C%.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 14.