计算C ++中GCD 1的子序列数
我们给了一个整数元素数组,任务是从给定数组中找出GCD为1的子序列。GCD是两个或多个整数的最大公约数,该整数将给定数字完全除,并且在所有数字中最大。
输入− int 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)
输入− int arr [] = {5,7,10}
输出-GCD 1的子序列数为-3
说明-
从给定数组中GCD为1可以形成的子序列是(5,7),(7,10),(5,7,10)
以下程序中使用的方法如下
输入任意给定大小的整数元素数组。
计算数组的大小并将数据传递给函数以进行进一步处理
声明一个临时变量计数以存储GCD为1的子序列数
从i到0开始循环直到数组大小
在循环内部,从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
以上是 计算C ++中GCD 1的子序列数 的全部内容, 来源链接: utcz.com/z/345391.html