You are viewing a single comment's thread. Return to all comments →
For Python3:
#!/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')
Hint for it:
If gcd(a,b) = x and gcd(a,b,c) = y, then y = gcd(x,c).
That is, if the array has gcd != 1, then none of its subsets will have gcd == 1. Otherwise, at least one subset will have gcd == 1.
Seems like cookies are disabled on this browser, please enable them to open this website
Sherlock and GCD
You are viewing a single comment's thread. Return to all comments →
For Python3:
Hint for it:
If gcd(a,b) = x and gcd(a,b,c) = y, then y = gcd(x,c).
That is, if the array has gcd != 1, then none of its subsets will have gcd == 1. Otherwise, at least one subset will have gcd == 1.