题目大意:
给定一序列 \(A\),定义当且仅当 \(\gcd(a_i,a_j)=a_{min}\) 时,元素 \(a_i\) 和 \(a_j\) 可以交换。
问当前给定的序列 \(A\) 能否转化为非严格单调递增的序列。
题目分析:
因为两个元素当且仅当其最大公因数为 \(a_{min}\) 时才可以交换,故我们可以先对原序列进行排序,然后判断排序后的序列中原序列与之间的不同的元素能不能被 \(a_{min}\) 整除即可,理由如下:
首先,很显然的是,原命题等价于两个命题,分别是:
- 若排序后的序列中与原序列之间不同的元素不能被 \(a_{min}\) 整除,则原序列必定无法转化为一个非严格单调递增的序列
- 若排序后的序列中与原序列之间的每一个不同的元素能被 \(a_{min}\) 整除,则原序列必定可以转化为一个非严格单调递增的序列。
现在,我们对命题 \(1\) 进行证明:
因为其为排序后的序列,故其与原序列不同的元素必然是那些发生了交换的元素。
如果那些发生了交换的元素不能被最小值 \(a_{min}\) 整除,则证明该元素中不完全包含 \(a_{min}\) 所含有的因子,故其与其他数的最大公因数必然不是\(a_{min}\),其显然无法完成交换操作,与前面相矛盾,所以无法完成转化操作。
现在,我们对命题 \(2\) 进行证明:
-
若每两个不同的元素之间的最大公因数为 \(a_{min}\),则其能转化为目标序列是显然的,这里不多赘述。
-
若有两个不同的元素之间的最大公因数不为 \(a_{min}\),那么这两个数要么可以通过其他与之最大公因数为 \(\boldsymbol{a_{min}}\) 的间接交换而来,要么直接和 \(a_{min}\) 间接交换而来。
综上,我们不难证明这个方法是正确的。时间复杂度取决于排序,这里我用的是快排,故时间复杂度为 \(O(n\lg n)\)
代码实现:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define TIME_LIMIT (time_t)2e3
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define MAX_SIZE (int)1.1e5
signed main() {
ios::sync_with_stdio(false);
#ifdef LOCAL
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
time_t cs = clock();
#endif
//========================================
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
int a[MAX_SIZE] = {};
int bak[MAX_SIZE] = {};
for (int i = 1; i <= n; i++) {
cin >> a[i];
bak[i] = a[i];
}
sort(a + 1, a + 1 + n);
bool flag = 0;
for (int i = 1; i <= n; i++) {
if (a[i] != bak[i] && a[i] % a[1] != 0) {
cout << "NO" << endl;
flag = 1;
break;
}
}
if (!flag)
cout << "YES" << endl;
}
//========================================
#ifdef LOCAL
fclose(stdin);
fclose(stdout);
time_t ce = clock();
cerr << "Used Time: " << ce - cs << " ms." << endl;
if (TIME_LIMIT < ce - cs)
cerr << "Warning!! Time exceeded limit!!" << endl;
#endif
return 0;
}
标签:CF1401C,min,int,题解,元素,序列,排序,公因数
From: https://www.cnblogs.com/larry76/p/17127353.html