반응형 유클리드호제법2 백준 14476번 최대공약수 하나 빼기 - C++ 풀이 1. 누적 gcd인 prefix gcd와 suffix gcd 배열을 구해둔다. 2. i번째 수를 제외한 나머지 수들의 gcd는 gcd(prefixGCD[i-1], suffixGCD[i+1])이다. 3. 각 수를 제외하는 모든 경우를 탐색하며 최대공약수가 최대가 되는 경우를 찾는다. 1. 누적 gcd인 prefix gcd와 suffix gcd 배열을 구해둔다. 어떤 수를 제외한 나머지 수들의 gcd를 O(1)에 구하기 위해 누적 gcd 배열을 활용할 것이다. A[0]~A[i] 까지의 최대 공약수는 prefixGCD[i], A[i]~A[N-1]까지의 최대공약수는 suffixGCD[i]라고 할 때, prefix GCD 배열과 suffix GCD 배열을 구해준다. 이 과정의 시간 복잡도는 O(N) 2. i번째 .. 2022. 6. 13. 백준 2981번 검문 - C++ 풀이 1. 두 수 a, b를 M으로 나눈 나머지가 같다면 (a-b) % M = 0 2. 두 수 a, b를 M으로 나눈 나머지가 같다면 M의 약수로 나눈 나머지도 같다. 3. A[i+1] - A[i](0 ≤ i < N-1)의 최대 공약수의 약수들이 가능한 모든 M이 된다. 1. 두 수 a, b를 M으로 나눈 나머지가 같다면 (a-b) % M = 0 두 수 a, b를 M으로 나눈 나머지가 r로 같다면, 두 수 a, b는 아래와 같이 나타낼 수 있다. a = M*(a/M) + r b = M*(b/M) + r 위 식에서 아래를 빼면 a-b = M*(a/M-b/M)이므로 (a-b)는 M으로 나누어 떨어진다. 2. 두 수 a, b를 M으로 나눈 나머지가 같다면 M의 약수로 나눈 나머지도 같다. 또한 두 수 a, b를 M.. 2022. 6. 9. 이전 1 다음 반응형
