정수 요소의 배열이 주어지고 주어진 배열에서 GCD가 1인 하위 시퀀스를 찾는 것이 작업입니다. GCD는 둘 이상의 최대 공약수입니다. 주어진 숫자를 전체와 가장 큰 숫자로 나누는 정수입니다.
입력 - 정수 arr[] ={3, 4, 8, 16}
출력 − GCD가 1인 하위 시퀀스의 수는 − 7입니다.
설명 -
GCD가 1인 주어진 배열에서 구성할 수 있는 부분 수열은 (3, 4), (3, 8), (3, 16), (4, 3), (8, 3), (16, 3), (3, 4, 8)
입력 - 정수 arr[] ={5, 7, 10}
출력 − GCD가 1인 하위 시퀀스의 수는 − 3입니다.
설명 -
GCD가 1인 주어진 배열에서 구성할 수 있는 하위 시퀀스는 (5, 7), (7, 10), (5, 7, 10)
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
주어진 크기의 정수 요소 배열을 입력하십시오.
-
배열의 크기를 계산하고 추가 처리를 위해 데이터를 함수에 전달합니다.
-
GCD가 1인 하위 시퀀스의 수를 저장하기 위해 임시 변수 수를 선언합니다.
-
배열의 크기까지 i에서 0까지 FOR 루프 시작
-
루프 내에서 배열의 크기까지 j에서 0까지 FOR 또 다른 루프를 시작합니다.
-
루프 내에서 IF GCD(arr[i], arr[j]) =TRUE를 확인한 다음 카운트를 1 증가시킵니다.
-
반품 횟수
-
결과를 인쇄하십시오.
예시
# include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
if (a == 0)
return b;
return gcd(b % a, a);
}
int GCD_1(int arr[],int size){
int count = 0;
for(int i=0;i<size;i++){
for(int j=0;j<=size;j++){
if(gcd(arr[i],arr[j])==1){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {3, 4, 8, 16};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Count of number of sub-sequences with GCD 1 are: "<<GCD_1(arr, size);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of number of sub-sequences with GCD 1 are: 7