간격의 최대 공약수-C++-php.cn

간격의 최대 공약수

WBOY

풀어 주다： 2023-09-01 10:09:06

앞으로

1275명이 탐색했습니다.

간격의 최대 공약수

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 = 상한/제수 - 하한/제수