[백준]13241 , 1735 , 2485

https://www.acmicpc.net/step/18

위 링크를 타고가면 , 약수와 배수 소수와 관련된 문제들을 볼 수 있다.

그중에서 13241 , 1735 , 2485 번은 모두 최대 공약수를 활용한 문제라는 것을 확인할 수 있다.
아래의 코드는 최대공약수를 찾는 문제가 나왔을 때 필수적으로 인지하고 있어야 하는 코드이다.

static long gcd(long a , long b){
    if(b==0) return a;
    return gcd(b , a%b);
}

유클리드 호제법 이라는 워딩으로 검색하면 많은 자료가 나오기 때문에 위 코드가 어떻게 최대공약수를 얻는지는 쉽게 찾아볼 수 있다.
아래는 내 나름대로 이해한 내용을 작성한 것이다.