P1414. 又是毕业季II

发表于 分类于 阅读次数： Waline： 本文字数： 272 阅读时长 ≈ 1 分钟

考点

  • 最大公约数

题解

见思路

思路

最多1e4个数据，用暴力搜索真的去模拟n个元素取k个还得两两取最大公约数...显然不现实

一个数的最大公约数是自己本身，所以有两种思路

枚举倍数

枚举这个数的倍数，显然有\[gcd\left( a,ax \right) =a\]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e6 + 50;
int n, cnt[LEN], w[LEN];

int main() {
  int in;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> in, ++cnt[in];
  for (int i = 1; i <= 1e6; ++i) {
    for (int j = i; j <= 1e6; j += i) {
      w[i] += cnt[j];
    }
  }
  for (int k = 1, i = 1e6; i >= 1 && k <= n; ++k) {
    while (w[i] < k) --i;
    cout << i << endl;
  }
  return 0;
}

枚举约数

任何一个数a，和它的约数b取最大公约数，显然等于b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e6 + 50;
int n, w[LEN];

int main() {
  int in;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> in;
    for (int j = 1; j <= in / j; ++j) {
      if (in % j) continue;
      ++w[j];
      if (j != in / j) ++w[in / j];
    }
  }
  for (int k = 1, i = 1e6; i >= 1 && k <= n; ++k) {
    while (w[i] < k) --i;
    cout << i << endl;
  }
  return 0;
}