문제는 주어진 범위에서 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() 함수를 사용하여 변수의 제수를 지속적으로 업데이트하여 범위의 최대 공약수를 얻습니다.
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 중국어 웹사이트의 기타 관련 기사를 참조하세요!