最长的子数组，其最大公约数大于1

数组是一组相似的数据集合，以连续的方式存储在相邻的内存位置上。通过将偏移值定义为数据库的特定基值，可以更容易地评估每个元素的特定位置。该特定索引的基值为零，偏移值是两个特定索引之间的差值。子数组是特定数组的一部分，可以定义为一组变量，具有多个值的标签。最长的子数组指的是数组中所有元素都大于K的数组。这里最大和子数组的和为-

• 给定数据集中的少于

• 等于给定的数据集。

• 给定数据集中的少于

要找到最长子数组的长度，我们只需要找出特定子数组中1的总数。注意：计数应该大于零的计数。最大公约数是一种数学现象，在其中我们找到可以将输入的整数中的每个整数除以零余数的最大整数值。这里的条件是，“最大公约数大于1”。这意味着，这里的特定数字在给定输入之间只有至少一个公共除数。

Input (array) : arr[] = {4, 3, 2, 2}
Output (after the process with sub-array operation) : 2
If we consider the subarray as {2, 2}, then we will get 2 as GCD. Which is > 1, is of maximum length.

今天在这篇文章中，我们将学习如何使用C++编程环境找到一个最长的子数组，其最大公约数大于1。

找到最长子数组的算法，其GCD大于1

在这个特定的算法中，我们可以找到包含大于1的最长子数组的最大公约数值。

• 第一步 - 开始。

• 第二步 - 声明进程的变量。

• 第三步 - 设置并将其初始化为零值。

• 第四步 - 创建一个函数来评估该子数组的最大长度。

• 步骤 5 - 将其作为参数包含一个向量。

• 第6步- 创建一个变量来获取答案。

• 第7步 - 设置并将其初始化为零值。

• 步骤8 - 存储具有GCD > 1值的最长子数组的值。

• 第9步 - 迭代循环以找到每个子数组的最大公约数。

• 第10步 - 用子数组的长度值替换答案。

• 步骤11 - 如果子数组的最大公约数大于1，则保存答案。

• 步骤12 - 返回答案。

• 步骤13 - 否则，再次运行循环并迭代。

• 第14步 - 在进程完成后终止。

查找最长子数组的语法，其GCD大于1

int n;
cin >> n;

const int MAX_NUM = 100 * 1000;
static int dp[MAX_NUM];

for(int i = 0; i < n; ++i){
   int x;
   cin >> x;

   int cur = 1;
   vector<int> d;
   for(int i = 2; i * i <= x; ++i){
      if(x % i == 0){
         cur = max(cur, dp[i] + 1);
         cur = max(cur, dp[x / i] + 1);
         d.push_back(i);
         d.push_back(x / i);
      }
   }
   if(x > 1){
      cur = max(cur, dp[x] + 1);
      d.push_back(x);
   }

    for(int j : d){
      dp[j] = cur;
   }
}
cout << *max_element(dp, dp + MAX_NUM) << endl;

通过遵循上述算法，我们在这里编写了可能的语法来找到具有大于1的最长子数组的GCD值。

方法：

• 方法1−通过朴素方法找到最长的子数组，其最大公约数大于1的C++程序。

• 方法2 - C++程序查找数组的最大公约数大于1。

使用朴素方法找到最长公约数大于1的子数组的C++程序

在这段C++代码中，我们采用了朴素的方法，通过生成给定数组的所有可能子数组，来找到具有大于1的最长子数组的GCD值。

Example 1

的中文翻译为：

示例1

#include <bits/stdc++.h>
using namespace std;
void maxSubarrayLen(int arr[], int n) {
	int maxLen = 0;
	for (int i = 0; i < n; i++) {
		int gcd = 0;
		for (int j = i; j < n; j++) {
			gcd = __gcd(gcd, arr[j]);
			if (gcd > 1)
				maxLen = max(maxLen, j - i + 1);
			else
			   break;
		}
	}
	cout << maxLen;
}
int main() {
	int arr[] = { 410, 16, 7, 180, 222, 10, 33 };
	int N = sizeof(arr) / sizeof(int);
	maxSubarrayLen(arr, N);

	return 0;
}

输出

3

C++程序查找数组的最大公约数大于1

在这段C++代码中，我们尝试计算最大公约数，并且它具有检查它是否大于1的能力。

Example 2

的翻译为：

示例2

#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
   if (a == 0)
      return b;
   return gcd(b%a, a);
}
void bestArray(int arr[], int n){
   bool even[n] = {false};
   int ans = 0;
   for(int i = 0; i < n; i++){
      ans = gcd(ans, arr[i]);
      if(arr[i] % 2 == 0)
         even[i] = true;
   }
   if(ans > 1)
      cout << 0 << endl;
   else {
      ans = 0;
      for(int i = 0; i < n-1; i++){
         if(!even[i]){
            even[i] = true;
            even[i+1] = true;
            if(arr[i+1]%2 != 0){
               ans+=1;
            }
            else
               ans+=2;
         }
      }
      if(!even[n-1]){
         ans+=2;
      }
      cout << ans << endl;
   }
}
int main(){
   int arr[] = {16, 10, 07, 81, 88, 32, 3, 42, 25};
   int n = 9;
   bestArray(arr, n);

   int arr1[] = {16, 7};
   n = 2;
   bestArray(arr1, n);

   int arr2[] = {10, 97, 2001};
   n = 3;
   bestArray(arr2, n);
}

输出

5
2
1

结论

通过这个讨论，我们可以找到如何找到最长的子数组，其GCD大于1。希望编写的算法和C++代码能够清晰地展示给你，让你了解这个过程在现实世界中是如何工作的。

以上是最长的子数组，其最大公约数大于1的详细内容。更多信息请关注PHP中文网其他相关文章！