锐客网

  1. 首页 > it技术 > >

codeforces C. Mere Array

codeforces

【codeforces C. Mere Array】codeforces C. Mere Array
文章图片

题目 题意： 给你一个序列，如果这个序列中的两个数满足 g c d ( a i , a j ) = m i n i = 1 n a gcd(a_i,a_j)=min^n_{i=1}a gcd(ai?,aj?)=mini=1n?a，那么这两个数字就可以进行置换，问最后能不能通过置换将这个序列变成一个不递减的序列。
思路： 如果要满足 g c d ( a i , a j ) = m i n i = 1 n a gcd(a_i,a_j)=min^n_{i=1}a gcd(ai?,aj?)=mini=1n?a，那么肯定有 a i % M i n = a j % M i n = 0 a_i\%Min=a_j\%Min=0 ai?%Min=aj?%Min=0，所以我们可以用 M i n Min Min进行交换，这样就可以不用考虑 g c d ( a i , a j ) = M i n gcd(a_i,a_j)=Min gcd(ai?,aj?)=Min是否成立了，因为有可能会出现 g c d ( a i , a j ) = M i n ? k gcd(a_i,a_j)=Min*k gcd(ai?,aj?)=Min?k，但是也可以通过 M i n Min Min实现置换。

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef vector veci; typedef vector vecl; typedef pair pii; typedef pair pll; template inline void read(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return ; while (c != '-' && (c < '0' || c > '9')) c = getchar(); sgn = (c == '-') ? -1:1; ret = (c == '-') ? 0:(c - '0'); while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return ; } inline void outi(int x) {if (x > 9) outi(x / 10); putchar(x % 10 + '0'); } inline void outl(ll x) {if (x > 9) outl(x / 10); putchar(x % 10 + '0'); } const int maxn = 1e5 + 10; int a[maxn] = {0}, b[maxn]; int main() { int t; read(t); while (t--) { int n, Min = 0x7fffffff; read(n); for (int i = 0; i < n; i++) read(a[i]), b[i] = a[i], Min = min(Min, a[i]); sort(a, a + n); bool flag = false; for (int i = 0; i < n; i++) { if (a[i] == b[i]) continue; else if (b[i] % Min != 0) { flag = true; break; } } if (!flag) printf("YES\n"); else printf("NO\n"); } return 0; }

    推荐阅读


    上一篇：codeforces D. Omkar and Bed Wars

    下一篇：codeforces B. Young Explorers