우리는 '시작', '종료', '숫자'의 세 가지 입력 변수를 제공했습니다. 목표는 GCD 값이 '숫자'와 같은 시작과 끝 사이의 숫자 쌍을 찾는 것입니다. 예를 들어 GCD(A,B)=number이고 A, B 모두 [start,end] 범위에 있습니다.
예를 들어 이해합시다.
입력 − 시작=5 끝=20 숫자=8
출력 − 주어진 숫자와 같은 GCD를 갖는 자연수 쌍의 개수는 − 3
설명 - GCD가 8이 되도록 5에서 20 사이의 쌍은 - (8,8), (8,16), (16,8)
입력 − 시작=5 끝=20 숫자=7
출력 − GCD가 주어진 수와 동일한 자연수 쌍의 개수는 − 2
설명 − GCD가 7이 되도록 20에서 30 사이의 쌍은 다음과 같습니다. - (21,28), (28,21)
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
우리는 두 가지 접근 방식을 사용할 것입니다. i=start에서 i<=end까지 for 루프와 j=start에서 j<=end까지 내부 루프를 사용하여 순회하는 첫 번째 순진한 접근 방식입니다. 각 쌍(i,j)에 대해 GCD(i,j)==숫자인지 확인합니다. true인 경우 카운트가 증가합니다.
-
변수 시작, 끝 및 숫자를 정수로 사용합니다.
-
함수 GCD(int a, int b)는 재귀적이며 전달된 인수 a,b의 GCD를 반환합니다.
-
b가 0이 아니면 자신을 재귀적으로 GCD(b,a%b)로 호출하고 그렇지 않으면 a를 반환합니다.
-
함수 GCD_pairs(int start, int end, int number)는 경계 변수 start, end 및 변수 number를 사용하고 gcd=number인 start와 end 사이의 쌍을 반환합니다.
-
초기 카운트를 0으로 합니다.
-
쌍의 각 구성원에 대해 두 개의 for 루프를 사용합니다. i=start에서 i<=end까지의 외부 루프 및 j=start에서 j<=end까지의 내부 루프.
-
쌍(i,j), GCD(i,j)==숫자인지 확인합니다. true이면 카운트를 증가시킵니다.
-
마침내 우리는 gcd=number인 쌍의 총 수를 얻을 것입니다.
-
결과로 카운트를 반환합니다.
효율적인 접근
이 접근 방식에서는 시작 및 끝 값을 업데이트합니다. pair(i,j)가 gcd=number를 가지려면 i,j 둘 다 '숫자'로 나눌 수 있어야 합니다. '숫자'를 완전히 나눌 최대 (끝-시작)/숫자 번호가 있을 것입니다. '숫자'로 나눌 수 있는 시작과 끝 사이의 숫자를 얻으려면 시작 =(시작 + 숫자 - 1) / 숫자에서 끝 =끝 / 숫자로 순회합니다. 따라서 이러한 각 숫자에 대해 gcd(i,j)==1이면 해당 쌍(i,j)에 대한 카운트를 증가시킵니다.
-
변수 시작, 끝 및 숫자를 정수로 사용합니다.
-
업데이트 시작 =(시작+숫자 - 1)/숫자. 그리고 end=end/number.
-
함수 GCD(int a, int b)는 재귀적이며 전달된 인수 a,b의 GCD를 반환합니다.
-
b가 0이 아니면 자신을 재귀적으로 GCD(b,a%b)로 호출하고 그렇지 않으면 a를 반환합니다.
-
함수 GCD_pairs(int start, int end, int number)는 경계 변수 start, end 및 변수 number를 사용하고 gcd=number인 start와 end 사이의 쌍을 반환합니다.
-
초기 카운트를 0으로 합니다.
-
쌍의 각 구성원에 대해 두 개의 for 루프를 사용합니다. i=start에서 i<=end까지의 외부 루프 및 j=start에서 j<=end까지의 내부 루프.
-
쌍(i,j), GCD(i,j)==1인지 확인합니다. true이면 카운트를 증가시킵니다.
-
마침내 우리는 gcd=number인 쌍의 총 수를 얻을 것입니다.
-
결과로 카운트를 반환합니다.
예(순진한 접근 방식)
#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b){
return b ? GCD(b, a % b) : a; }
int GCD_pairs(int start, int end, int number){
int count = 0;
for (int i = start; i <= end; i++){
for (int j = start; j <= end; j++){
if (GCD(i, j) == number){
count++;
}
}
}
return count;
}
int main(){
int start = 10, end = 30, number = 10;
cout<<"Count of pairs of natural numbers with GCD equal to given number are: "<<GCD_pairs(start, end, number) << endl;
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of pairs of natural numbers with GCD equal to given number are: 7
예(효율적인 접근)
#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b){
return b ? GCD(b, a % b) : a;
}
int GCD_pairs(int start, int end, int number){
int count = 0;
for (int i = start; i <= end; i++){
for (int j = start; j <= end; j++){
if (GCD(i, j) == 1){
count++;
}
}
}
return count;
}
int main(){
int start = 10, end = 30, number = 10;
start = (start + number - 1) / number;
end = end / number;
cout<<"Count of pairs of natural numbers with GCD equal to given number are: "<<GCD_pairs(start, end, number) << endl;
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of pairs of natural numbers with GCD equal to given number are: 7