博客

A. Serval and Mocha’s Array

原题链接 Problem – A – Codeforces

官方题解：

考虑n(n≥2)个正整数数组a，当2≤i≤n时，不等式成立:gcd(a1,a2，⋯，ai)≤gcd(a1,a2)≤2

因此，当a的前缀[a1,a2]是好的，我们可以证明a的所有长度不小于2的前缀都是好的，则a是美丽的。很明显，当a是美的时候，[a1,a2]是好的。所以我们得出结论，当且仅当前缀[a1,a2]是好的。

我们可以检验是否存在ai,aj (i≠j)使得gcd(ai,aj)≤2。如果是这样，我们可以将ai,aj移到a的前面，使它更漂亮，那么答案是Yes。如果没有，答案是否定的。

时间复杂度:O(n2log106)。

其实就是只要存在两个数的最大公约数<=2就说明整个数组都是beautiful的

#include <iostream>
#include <algorithm>
using namespace std ;
int n , T ;
const int N = 110 ;
int a[N];

int gcd(int a , int b){
    return b > 0 ? gcd(b , a%b) : a ;
}

int main()
{
    a[0] = 1;
    scanf("%d", &T);
    while( T -- ){
        scanf("%d" , &n);
        for(int i = 0 ; i < n ;i ++ ){
            scanf("%d",&a[i]);
        }
        bool beautiful = false;
        //只要存在两个数的最大公约数<=2就说明整个数组都是beautiful的
        for (int i = 0; i < n; i ++ ) {
            for (int j = i + 1; j < n; j ++ ) {
                if (gcd(a[i], a[j]) <= 2) beautiful = true;
            }
        }
        if (beautiful) cout << "Yes\n";
        else cout << "No\n";
    }
}