转换数组,以使数组的GCD在C ++中变为1
在本教程中,我们将讨论一个程序来转换数组,以使数组的GCD变为1。
为此,我们将提供一个数组和一个正整数k。我们的任务是转换数组元素,以使元素的GCD为1,同时仅将数组元素除以k任意次,直到元素小于k。
示例
#include <bits/stdc++.h>
using namespace std;
//计算数组的GCD-
int calculate_gcd(int* arr, int n){
int gcd = arr[0];
for (int i = 1; i < n; i++)
gcd = __gcd(arr[i], gcd);
return gcd;
}
//检查操作是否可行
bool convertGcd(int* arr, int n, int k){
int gcd = calculate_gcd(arr, n);
int max_prime = 1;
for (int i = 2; i <= sqrt(gcd); i++) {
while (gcd % i == 0) {
gcd /= i;
max_prime = max(max_prime, i);
}
}
max_prime = max(max_prime, gcd);
return (max_prime <= k);
}
int main(){
int arr[] = { 10, 15, 30 };
int k = 6;
int n = sizeof(arr) / sizeof(arr[0]);
if (convertGcd(arr, n, k) == true)
cout << "Yes";
else
cout << "No";
return 0;
}输出结果
Yes
热门推荐
1 训练狗狗搜寻
2 如何训练狗狗装死
3 狗狗训练书
6 怎么训练狗狗拜年
8 狗狗训练游戏
10 狗狗嗅觉训练
11 怎么训练狗狗在笼子里不叫
12 怎么训练狗狗站立走路
13 怎么训练狗狗在马桶上
14 狗狗尿尿怎么训练
15 训练狗狗用品
16 泰迪狗狗的训练方法大小便
17 训练狗狗可以打吗
18 王曼丽的狗狗训练