목록백준 2981 (1)

시작이 반

[백준] 2981번 (python 파이썬)

수학적 이론이 필요한 문제이다. M 을 찾아야한다. A = M * a + R B = M * b + R C = M * c + R 여기서 R을 제거하면 A - B = M ( a - b ) B - C = M ( b - c ) 이런 식이 나온다. 즉, M은 A-B, B-C의 공약수이다 즉 최대공약수를 구하면 된다. 최대 공약수를 구하고 해당 수의 1을 제외한 약수를 출력하면된다. 이때 최대 공약수를 구하고 약수를 구할때 반복문을 최대공약수 까지 돌려버리면 숫자 범위가 1,000,000,000까지기 때문에 엄청난 시간이 걸린다. 그래서 공약수를 구할때 18 % 2 = 0 ( 2 = 약수) 18 // 2 = 9 ( 9 = 약수) 이 2개를 한번에 구한다 이러면 반복횟수를 최대공약수의 제곱근 까지 줄일수 있다. 마지..
알고리즘/백준 2021. 3. 1. 19:42
이전 Prev 1 Next 다음