计算C ++中GCD 1的子序列数
我们给了一个整数元素数组，任务是从给定数组中找出GCD为1的子序列。GCD是两个或多个整数的最大公约数，该整数将给定数字完全除，并且在所有数字中最大。
输入−intarr[]={3，4，8，16}
输出-GCD1的子序列数为-7
说明-
从给定数组中GCD为1可以形成的子序列是(3,4)，(3,8)，(3,16)，(4,3)，（8、3），（16，3），（3、4、8）
输入−intarr[]={5，7，10}
输出-GCD1的子序列数为-3
说明-
从给定数组中GCD为1可以形成的子序列是(5,7)，(7,10)，(5,7,10)
以下程序中使用的方法如下
输入任意给定大小的整数元素数组。
计算数组的大小并将数据传递给函数以进行进一步处理
声明一个临时变量计数以存储GCD为1的子序列数
从i到0开始循环直到数组大小
在循环内部，从j到0直到数组大小开始另一个循环FOR
在循环内，检查IFGCD（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