fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. int gcd(int a, int b) {
  6.     if (b == 0) return a;
  7.     return gcd(b, a % b);
  8. }
  9.  
  10. bool is_good(int a[], int n) {
  11.     int g = a[0];
  12.     for (int i = 1; i < n; i++) {
  13.         g = gcd(g, a[i]);
  14.     }
  15.     return g <= n;
  16. }
  17.  
  18. bool is_beautiful(int a[], int n) {
  19.     for (int i = 2; i <= n; i++) {
  20.         if (!is_good(a, i)) {
  21.             return false;
  22.         }
  23.     }
  24.     return true;
  25. }
  26.  
  27. int main() {
  28.     int t;
  29.     cin >> t;
  30.     while (t--) {
  31.         int n;
  32.         cin >> n;
  33.         int a[n];
  34.         for (int i = 0; i < n; i++) {
  35.             cin >> a[i];
  36.         }
  37.         if (is_beautiful(a, n)) {
  38.             cout << "Yes\n";
  39.         } else {
  40.             sort(a, a + n, greater<int>());
  41.             if (is_beautiful(a, n)) {
  42.                 cout << "Yes\n";
  43.             } else {
  44.                 cout << "No\n";
  45.             }
  46.         }
  47.     }
  48.     return 0;
  49. }
  50.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
6
2
3 6
3
1 2 4
3
3 6 1
3
15 35 21
4
35 10 35 14
5
1261 227821 143 4171 1941
stdout
copy 
No
Yes
No
No
No
Yes
https://ideone.com/2jthZR
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!