題目概述

原題參考：D. Turtle Tenacity: Continual Mods
給出長度為n的數組，可以對其任意排列，問是否可以給出一個數組a1、a2...、an滿足a1%a2%...%an!= 0

思路想法

感覺這種與順序無關的題目都可以先嘗試升序或是降序排列，事實上，假如升序排列，如果最小值a1只有一個的話，那么最終答案就是a1，但是如果存在多個最小值該如何，此時應該選出一個除最小值之外的數，對最小值進行取模運算，得出一個更小的數，答案就是這個數，當然，當其余數對最小值取模得出的結果都是0時，那么就沒有答案，對于這個，可以記錄數組的gcd，只要最小值不是gcd就可以

參考代碼

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 2e5+7;
int n, a[N], minA, _gcd = 0;
map<int, int> cnt;
void solve() {
    cin >> n;
    cnt.clear(), _gcd = 0;
    minA = 1e9+7;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        cnt[a[i]] ++;
        minA = min(minA, a[i]);
        _gcd = gcd(_gcd, a[i]);
    }
    if(cnt[minA] == 1) cout << "YES" << endl;
    else {
        if(minA == _gcd) cout << "NO" << endl;
        else {
            if(cnt[minA] != n) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
}
int main() {
#ifdef xrl
    freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
    FAST_IO;
    int t = 1;
    cin >> t;
    while(t --) solve();
#ifdef xrl
    cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
    return 0;
}

做題反思

對于與順序無關的題目，往往可以先嘗試升序或是降序排列。同時，對于大多數題目，都可以先考慮簡單情況再由復雜情況入手