간격의 최대 공약수

x와 y를 두 개의 숫자로 둡니다. 이 경우, y를 x로 나눌 때 나머지가 0인 경우 x는 y의 제수라고 합니다. 구간에서 발생하는 가장 큰 약수는 구간에 있는 요소의 가장 큰 수의 약수입니다.

문제 설명

간격 [a, b]가 주어졌습니다. a와 b를 포함하는 범위("1" 제외)에서 나타나는 가장 큰 제수를 찾습니다. 모든 제수가 동일한 횟수로 나타나는 경우 1을 반환합니다.

예 1

으아악 으아악

설명 - 2의 약수 = {1, 2}, 3의 약수 = {1, 3}, 4의 약수 = {1, 2, 4}, 5의 약수 = {1, 5} . 2는 가장 빈번한 약수입니다.

예 2

으아악 으아악

설명 - 2의 약수 = {1, 2}, 3의 약수 = {1, 3}, 4의 약수 = {1, 2, 4}, 5의 약수 = {1, 5} . 2는 가장 빈번한 약수입니다.

방법 1: 무차별 크래킹

이 문제를 해결하는 무차별적인 방법은 간격에 있는 모든 숫자의 모든 약수를 찾아 발생 횟수와 함께 맵에 저장하는 것입니다.

알고리즘

프로세스 제수(숫자)

• For i = 1 to n1/2+1

• 숫자%i == 0

인 경우

• 숫자/i == i

인 경우

• 지도에 i가 없으면 (i, 1)을 삽입하세요

• 그렇지 않으면 지도[i]++

• 기타

• 지도에 i가 없으면 (i, 1)을 삽입하세요

• 그렇지 않으면 지도[i]++

• num/i가 맵에 없으면 (num/i, 1)을 삽입하세요

• 다른 지도[num/i]++

maxDivisors(a, b) 처리

• n=a에서 b까지

• 제수(n)

• map.erase(1)

• divisor = 1, 개수 = int_min

• 지도의 모든 요소에

• if it.value > count

• count = it.value

• Divisor = it.key

예: C++ 구현

아래 프로그램에서는 divisors() 함수에서 각 숫자의 제수를 찾고, maxdivisor() 함수에서 가장 큰 발생 제수를 찾습니다.

으아악

출력

으아악

시간 복잡도 - O(n3/2), 간격의 각 숫자에 대해 제수를 찾기 위해 복잡도 O(n1/2)의 루프가 수행되기 때문입니다.

공간 복잡성 - O(n), 지도 공간.

방법 2

제수가 나올 때마다 지도를 채우는 시간을 줄임으로써 위의 방법을 더욱 최적화할 수 있습니다. 각 숫자의 약수를 찾는 대신 구간의 하한과 상한을 계산하여 구간에서 각 약수가 발생하는 것을 학습할 수 있습니다.

구간 [2, 5]를 예로 들어보겠습니다.

가능한 약수의 집합은 1부터 5까지입니다. 따라서 1 = 5/1 - 2/1 +1 = 4가 발생합니다. 2 = 5/2 - 2/2 + 1 = 2인 것으로 보입니다. 3 = 5/3 - 2/3 = 1인 것으로 보입니다. 4 = 5/4 - 2/4 = 1인 것으로 보입니다. 5 = 5/5 - 2/5 = 1인 것으로 보입니다.

위의 내용은 다음과 같이 공식화할 수 있습니다.

하한% 제수 == 0이면 occ = 상한/제수 - 하한/제수 + 1

기타 occ = 상한/제수 - 하한/제수

알고리즘

maxDivisor(a, b) 프로세스

• for i = 2 to b

• 만약 a%i == 0

• 회수 = b/i - a/i +1

• 기타

• 회수 = b/i - a/i

• map.insert(i, 시간)

• divisor = 1, 개수 = int_min

• 지도의 모든 요소에

• if it.value > count

• count = it.value

• Divisor = it.key

예: C++ 구현

아래 프로그램에서는 숫자의 제수를 역순으로 찾는 대신 각 제수에 대해 간격에 몇 개의 배수가 있는지 찾습니다.

으아악

출력

으아악

방법 3

이 문제에 대한 매우 간단한 해결책이 아래에 나와 있습니다.

크기가 1보다 큰 간격에서는 숫자의 절반(모든 짝수)이 약수로 2를 갖게 됩니다.

그래서 다음과 같이 사용할 수 있습니다.

알고리즘

maxDivisors(a, b) 처리

• 만약 a == b

• ans =

• 기타

• ans = 2

예: C++ 구현

아래 프로그램에서는 모든 짝수가 약수로 2를 갖는다는 관찰을 구현합니다.

으아악

출력

으아악

결론

간단히 말하면, 간격에서 가장 큰 발생 약수를 찾기 위해 위의 방법을 사용할 수 있으며, 시간 범위는 O(n3/2)부터 O(1)까지이고 공간 범위는 O(n)까지입니다. O( 1).

위 내용은 간격의 최대 공약수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!