用 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)

下面程序中使用的方法如下

  • 输入任意大小的整数元素数组。

  • 计算数组的大小并将数据传递给函数以进行进一步处理

  • 声明一个临时变量 count 用于存储 GCD 为 1 的子序列的计数

  • 从 i 为 0 开始循环到数组的大小

  • 在循环内部，从 j 为 0 开始另一个循环到数组的大小

  • 在循环内部，检查 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

更新于: 2020-08-31

287 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告