给定一个正元素数组和一个正整数k，任务是将数组的GCD转换为1。为了实现这一点，任意次数只允许进行一次操作，即选择数组中的任何元素，并用数字d除以，其中d<=k。 例如：
null
输入：arr={10,15,30}，k=6 输出：是的 按原样将数组的所有元素除以5 所有元素的除数，也小于k，即6。 它给出了类似于{2,3,6}的序列。现在，分开 2乘2，3乘3，6乘2。然后是序列 变成{1,1,3}。现在，阵列的gcd为1。 输入：arr={5,10,20}，k=4 输出：否 这里，将10除以2，序列变为 {5, 5, 20}. 然后，将20除以2，再除以2。 最后，序列变成{5,5,5}。使 序列1的gcd除以每个元素 五点之前。但是5>4，所以这里不可能 gcd 1。
方法：
- 如果存在一个大于k的正素数，将数组中的每个元素分开，那么答案是否定的。
- 如果数组的GCD的最大素因子小于或等于k，则答案是肯定的。
- 首先，找到数组的GCD，然后检查GCD的素因子是否大于k。
- 为此，计算GCD的最大素因子。
C++
// C++ program to check if it is // possible to convert the gcd of // the array to 1 by applying the // given operation #include <bits/stdc++.h> using namespace std; // Function to get gcd of the array. int getGcd( int * arr, int n) { int gcd = arr[0]; for ( int i = 1; i < n; i++) gcd = __gcd(arr[i], gcd); return gcd; } // Function to check if it is possible. bool convertGcd( int * arr, int n, int k) { // Getting the gcd of array int gcd = getGcd(arr, n); // Initially taking max_prime factor is 1. int max_prime = 1; // find maximum of all the prime factors // till sqrt(gcd). for ( int i = 2; i <= sqrt (gcd); i++) { while (gcd % i == 0) { gcd /= i; max_prime = max(max_prime, i); } } // either GCD is reduced to 1 or a prime factor // greater than sqrt(gcd) max_prime = max(max_prime, gcd); return (max_prime <= k); } // Drivers code 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; } |
JAVA
// Java program to check if it is // possible to convert the gcd of // the array to 1 by applying the // given operation import java.io.*; class GFG { // Recursive function to return // gcd of a and b static int __gcd( int a, int b) { // Everything divides 0 if (a == 0 || b == 0 ) return 0 ; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a-b, b); return __gcd(a, b-a); } // Function to get gcd of the array. static int getGcd( int arr[], int n) { int gcd = arr[ 0 ]; for ( int i = 1 ; i < n; i++) gcd = __gcd(arr[i], gcd); return gcd; } // Function to check if it is possible. static boolean convertGcd( int []arr, int n, int k) { // Getting the gcd of array int gcd = getGcd(arr, n); // Initially taking max_prime // factor is 1. int max_prime = 1 ; // find maximum of all the prime // factors till sqrt(gcd). for ( int i = 2 ; i <= Math.sqrt(gcd); i++) { while (gcd % i == 0 ) { gcd /= i; max_prime = Math.max(max_prime, i); } } // either GCD is reduced to 1 or a // prime factor greater than sqrt(gcd) max_prime = Math.max(max_prime, gcd); return (max_prime <= k); } // Drivers code public static void main (String[] args) { int []arr = { 10 , 15 , 30 }; int k = 6 ; int n = arr.length; if (convertGcd(arr, n, k) == true ) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by anuj_67. |
Python3
# Python 3 program to check if it is # possible to convert the gcd of # the array to 1 by applying the # given operation from math import gcd as __gcd, sqrt # Function to get gcd of the array. def getGcd(arr, n): gcd = arr[ 0 ]; for i in range ( 1 , n, 1 ): gcd = __gcd(arr[i], gcd) return gcd # Function to check if it is possible. def convertGcd(arr, n, k): # Getting the gcd of array gcd = getGcd(arr, n) # Initially taking max_prime # factor is 1. max_prime = 1 # find maximum of all the # prime factors till sqrt(gcd) p = int (sqrt(gcd)) + 1 for i in range ( 2 , p, 1 ): while (gcd % i = = 0 ): gcd = int (gcd / i) max_prime = max (max_prime, i) # either GCD is reduced to 1 or a # prime factor greater than sqrt(gcd) max_prime = max (max_prime, gcd) return (max_prime < = k) # Drivers code if __name__ = = '__main__' : arr = [ 10 , 15 , 30 ] k = 6 n = len (arr) if (convertGcd(arr, n, k) = = True ): print ( "Yes" ) else : print ( "No" ) # This code is contributed by # Sahil_Shelangia |
C#
// C# program to check if it is // possible to convert the gcd of // the array to 1 by applying the // given operation using System; class GFG { // Recursive function to return // gcd of a and b static int __gcd( int a, int b) { // Everything divides 0 if (a == 0 || b == 0) return 0; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a-b, b); return __gcd(a, b-a); } // Function to get gcd of the array. static int getGcd( int []arr, int n) { int gcd = arr[0]; for ( int i = 1; i < n; i++) gcd = __gcd(arr[i], gcd); return gcd; } // Function to check if it is possible. static bool convertGcd( int []arr, int n, int k) { // Getting the gcd of array int gcd = getGcd(arr, n); // Initially taking max_prime // factor is 1. int max_prime = 1; // find maximum of all the prime // factors till sqrt(gcd). for ( int i = 2; i <= Math.Sqrt(gcd); i++) { while (gcd % i == 0) { gcd /= i; max_prime = Math.Max(max_prime, i); } } // either GCD is reduced to 1 or a // prime factor greater than sqrt(gcd) max_prime = Math.Max(max_prime, gcd); return (max_prime <= k); } // Drivers code public static void Main () { int []arr = { 10, 15, 30 }; int k = 6; int n = arr.Length; if (convertGcd(arr, n, k) == true ) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by anuj_67. |
PHP
<?php // PHP program to check if it is // possible to convert the gcd of // the array to 1 by applying the // given operation // Recursive function to // return gcd of a and b function __gcd( $a , $b ) { // Everything divides 0 if ( $a == 0 or $b == 0) return 0 ; // base case if ( $a == $b ) return $a ; // a is greater if ( $a > $b ) return __gcd( $a - $b , $b ) ; return __gcd( $a , $b - $a ) ; } // Function to get gcd of the array. function getGcd( $arr , $n ) { $gcd = $arr [0]; for ( $i = 1; $i < $n ; $i ++) $gcd = __gcd( $arr [ $i ], $gcd ); return $gcd ; } // Function to check if it is possible. function convertGcd( $arr , $n , $k ) { // Getting the gcd of array $gcd = getGcd( $arr , $n ); // Initially taking max_prime // factor is 1. $max_prime = 1; // find maximum of all the prime // factors till sqrt(gcd). for ( $i = 2; $i <= sqrt( $gcd ); $i ++) { while ( $gcd % $i == 0) { $gcd /= $i ; $max_prime = max( $max_prime , $i ); } } // either GCD is reduced // to 1 or a prime factor // greater than sqrt(gcd) $max_prime = max( $max_prime , $gcd ); return ( $max_prime <= $k ); } // Driver Code $arr = array (10, 15, 30); $k = 6; $n = count ( $arr ); if (convertGcd( $arr , $n , $k ) == true) echo "Yes" ; else echo "No" ; // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to check if it is // possible to convert the gcd of // the array to 1 by applying the // given operation // Recursive function to return // gcd of a and b function __gcd(a, b) { // Everything divides 0 if (a == 0 || b == 0) return 0; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a-b, b); return __gcd(a, b-a); } // Function to get gcd of the array. function getGcd(arr, n) { let gcd = arr[0]; for (let i = 1; i < n; i++) gcd = __gcd(arr[i], gcd); return gcd; } // Function to check if it is possible. function convertGcd(arr, n, k) { // Getting the gcd of array let gcd = getGcd(arr, n); // Initially taking max_prime // factor is 1. let max_prime = 1; // find maximum of all the prime // factors till sqrt(gcd). for (let i = 2; i <= Math.sqrt(gcd); i++) { while (gcd % i == 0) { gcd = parseInt(gcd / i, 10); max_prime = Math.max(max_prime, i); } } // either GCD is reduced to 1 or a // prime factor greater than sqrt(gcd) max_prime = Math.max(max_prime, gcd); return (max_prime <= k); } let arr = [ 10, 15, 30 ]; let k = 6; let n = arr.length; if (convertGcd(arr, n, k) == true ) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by divyesh072019. </script> |
输出：
Yes
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
