Soluție HackerRank pentru Sherlock and GCD, subdomeniul Number Theory, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Sherlock and GCD
- Domeniu: Number Theory
- Limbaj: Python 3
Challenge: Sherlock and GCD
Subdomeniu: Number Theory (number-theory)
Scor cont: 20.0 / 20
Submission status: Accepted
Submission score: 1.0
Submission ID: 464722551
Limbaj: python3
Link challenge: https://www.hackerrank.com/challenges/sherlock-and-gcd/problem
Cerință
Sherlock is stuck while solving a problem: Given an array A = {a_1, a_2, ·s, a_N }, he wants to know if there exists a subset B of this array which follows these statements:
* B is a non-empty subset.
* There exists no integer x (x > 1) which divides all elements of B.
* There are no elements of B which are equal to another.
Input Format
The first line of input contains an integer, T, representing the number of test cases. Then T test cases follow.
Each test case consists of two lines. The first line contains an integer, N, representing the size of array A. In the second line there are N space-separated integers, a_1, a_2, …, a_n, representing the elements of array A.
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 100
1 ≤ a_i ≤ 10^5 text{ } forall 1≤ i ≤ N
Output Format
Print `YES` if such a subset exists; otherwise, print `NO`.
Cod sursă
#!/bin/python3
import functools as ft
def gcd(a,b):
if a < b:
a,b = b,a
if not a % b:
return b
else:
return gcd(b, a % b)
for _ in range(int(input())):
n = int(input())
array = [int(temp) for temp in input().split()]
print('YES' if ft.reduce(gcd, array) == 1 else 'NO')