x와 y를 두 개의 숫자로 둡니다. 이 경우, y를 x로 나눌 때 나머지가 0인 경우 x는 y의 제수라고 합니다. 구간에서 발생하는 가장 큰 약수는 구간에 있는 요소의 가장 큰 수의 약수입니다.
간격 [a, b]가 주어졌습니다. a와 b를 포함하는 범위("1" 제외)에서 나타나는 가장 큰 제수를 찾습니다. 모든 제수가 동일한 횟수로 나타나는 경우 1을 반환합니다.
설명 - 2의 약수 = {1, 2}, 3의 약수 = {1, 3}, 4의 약수 = {1, 2, 4}, 5의 약수 = {1, 5} . 2는 가장 빈번한 약수입니다.
설명 - 2의 약수 = {1, 2}, 3의 약수 = {1, 3}, 4의 약수 = {1, 2, 4}, 5의 약수 = {1, 5} . 2는 가장 빈번한 약수입니다.
이 문제를 해결하는 무차별적인 방법은 간격에 있는 모든 숫자의 모든 약수를 찾아 발생 횟수와 함께 맵에 저장하는 것입니다.
프로세스 제수(숫자)
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
아래 프로그램에서는 divisors() 함수에서 각 숫자의 제수를 찾고, maxdivisor() 함수에서 가장 큰 발생 제수를 찾습니다.
으아악시간 복잡도 - O(n3/2), 간격의 각 숫자에 대해 제수를 찾기 위해 복잡도 O(n1/2)의 루프가 수행되기 때문입니다.
공간 복잡성 - O(n), 지도 공간.
제수가 나올 때마다 지도를 채우는 시간을 줄임으로써 위의 방법을 더욱 최적화할 수 있습니다. 각 숫자의 약수를 찾는 대신 구간의 하한과 상한을 계산하여 구간에서 각 약수가 발생하는 것을 학습할 수 있습니다.
구간 [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
아래 프로그램에서는 숫자의 제수를 역순으로 찾는 대신 각 제수에 대해 간격에 몇 개의 배수가 있는지 찾습니다.
으아악이 문제에 대한 매우 간단한 해결책이 아래에 나와 있습니다.
크기가 1보다 큰 간격에서는 숫자의 절반(모든 짝수)이 약수로 2를 갖게 됩니다.
그래서 다음과 같이 사용할 수 있습니다.
maxDivisors(a, b) 처리
만약 a == b
ans =
기타
ans = 2
아래 프로그램에서는 모든 짝수가 약수로 2를 갖는다는 관찰을 구현합니다.
으아악간단히 말하면, 간격에서 가장 큰 발생 약수를 찾기 위해 위의 방법을 사용할 수 있으며, 시간 범위는 O(n3/2)부터 O(1)까지이고 공간 범위는 O(n)까지입니다. O( 1).
위 내용은 간격의 최대 공약수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!