주어진 범위에서 최대 공약수 찾기

문제는 주어진 범위에서 GCD를 찾아야 한다는 것입니다. 우리는 [p,q] 범위에서 두 개의 양의 정수 x와 y와 두 개의 정수 p와 q를 얻게 됩니다. [p,q] 범위에 속하는 숫자 x와 y의 GCD(최대 공약수)를 찾아야 합니다. 수학에서 최대 공약수로 알려진 GCD는 주어진 양의 정수 두 개를 나누는 가장 큰 양의 정수입니다. 주어진 정수는 0이 아니어야 합니다. 임의의 두 양의 정수 x와 y에 대해서는 gcd(x,y)로 표현됩니다.

예를 들어 두 개의 양의 정수 6과 9가 있습니다. 최대 공약수 gcd(6,9)는 이 두 숫자를 나누는 가장 큰 숫자이기 때문에 3이 됩니다.

하지만 이 문제에서는 지정된 범위 내에서 주어진 두 양의 정수의 최대 공약수를 찾아야 합니다. 예를 통해 이 문제를 이해해 보자. 이 숫자의 gcd를 찾기 위해 입력 x와 y로 4개의 숫자가 주어지고, gcd의 범위를 나타내는 두 개의 숫자, 즉 [p,q]가 제공됩니다.

입력: x=8, y=12, p=1, q=3

출력: 2

설명 - 주어진 두 숫자 x와 y의 최대 공약수는 4이므로 그러나 4는 [1,3] 범위에 없습니다. [1,3] 범위의 최대 공약수는 2이며, 이는 우리가 원하는 출력입니다.

입력: x=17, y=15, a=5, b=10

출력: -1

설명 - 17과 15의 최대공약수는 1입니다. 1이 주어진 범위 [5,10]에 없기 때문입니다. 주어진 범위에 공약수가 없으면 출력으로 -1을 인쇄해야 합니다.

알고리즘

문제를 해결하기 위해 사용하는 알고리즘은 매우 간단하고 수학적으로 관련되어 있습니다. 먼저 숫자 x와 y의 gcd(최대 공약수)를 찾습니다. C++에는 숫자의 최대 공약수를 출력으로 반환하는 gcd()라는 내장 함수가 있습니다.

문법

으아악

유클리드 알고리즘의 효율적인 방법을 사용하여 두 숫자의 gcd를 찾을 수도 있습니다. 둘 다 동시에 작동하며 시간 복잡도는 O(log(min(x,y))입니다.

이제 간단한 산술 법칙을 사용하여 두 숫자의 gcd를 나누는 숫자가 두 숫자 자체로도 나누어진다는 결론을 내릴 수 있습니다 . 따라서 for 루프에서 i=1부터 sqrt(gcd(x,y))까지 반복하면 숫자의 모든 공약수를 얻는 데 도움이 됩니다.

그런 다음 각 i가 sqrt(gcd(x,y))까지 gcd(x,y)로 나뉘는지 확인하세요. i가 gcd(x,y)를 나누면 gcd(x,y)/i도 gcd의 약수라고 말할 수 있습니다. 따라서 이 값은 숫자 x와 y의 공약수도 된다는 결론을 내릴 수 있습니다.

예를 통해 이 개념을 이해해 보겠습니다. x와 y가 각각 32와 48이라고 가정합니다. gcd(18,27)은 16입니다. 따라서 이 경우 i=1에서 i

참고 - 숫자 n을 숫자 x로 나누어 y를 얻으면 $frac{n}{x}:=:y$로 표현될 수 있으며 y는 n을 x $(x:times: y:=: n)$.

이 알고리즘은 아마도 이 문제를 해결하는 가장 효율적인 방법일 것입니다. 이 알고리즘을 따르면서 우리는 공통분모가 [a,b] 범위에 있는지 지속적으로 확인하게 됩니다. 그렇지 않은 경우 max() 함수를 사용하여 변수의 제수를 지속적으로 업데이트하여 범위의 최대 공약수를 얻습니다.

max() 함수 구문

으아악

a와 b의 최대값을 반환합니다.

방법

우리가 따를 접근 방식은 다음과 같습니다. -

• 주어진 범위 내에서 최대 공약수를 계산하는 함수를 초기화하세요.

• 주어진 두 양수 x와 y의 gcd를 계산하세요.

• 변수 이름 ans = -1을 초기화합니다.

• for 루프에서 i=1부터 i

• (gcd(x,y)%i)=0인 경우 i가 [a,b] 범위에 있는지 확인하고 max() 함수를 사용하여 이를 ans에 저장하여 다음 위치에 있는 최대 공약수를 얻습니다. 범위 내.

• gcd/i가 범위 내에 있는지도 확인하세요. 범위 내에 있으면 max() 함수를 다시 사용하여 ans 값을 업데이트하세요.

• for 루프에서 모든 반복을 완료한 후 ans를 반환합니다.

예

C++에서 이 메서드 구현 -

으아악

출력

으아악

시간 복잡도: O(log(min(x,y)) + sqrt(z)), 여기서 z는 두 숫자 x와 y의 최대 공약수입니다.

공간 복잡도: O(1), 추가 공간이 사용되지 않기 때문입니다.

결론

[a,b] 범위에 있는 두 숫자의 gcd 문제를 해결하는 방법을 논의했습니다. 이것이 다양한 함수를 사용하여 C++에서 위의 문제를 해결할 수 있는 방법입니다.

이 문서가 도움이 되었고 이 문제와 관련된 모든 개념을 명확히 하였기를 바랍니다.

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