[Codeforces520D] Fun with Integers (规律，并查集)

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：http://codeforces.com/contest/1062/problem/D

给一个$n$，现在允许任意初始一个数$k$并给定一个操作：$ax=b$，$bx=a$当且仅当$a$为$b$的倍数或$b$为$a$的倍数时，可以将$a$变为$b$（可以是负数），同时获得分数$|x|$. 要求不允许有多次$a$到$b$或$b$到$a$的操作（每个$x$仅算一次），问最多能得多少分。

看到第一个样例就明白了：考虑一个数$x$和它的因数$p_i$，我们总可以由$x$转到所有$\pm p_i$的可能（从$x$转到$p_i$，再由$p_i$转到$-x$，然后是$-x$到$-p_i$，接着是$-p_i$到$x$），每一次的贡献是$4p_i$，于是我们考虑维护所有带有整除关系的连通块，然后计算它们的所有倍数和*4就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int maxn = 100100;
int n;
int pre[maxn];
LL s[maxn];

int find(int x) {
  return x == pre[x] ? x : pre[x] = find(pre[x]);
}

void unite(int x, int y) {
  pre[find(x)] = find(y);
}

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d", &n)) {
    for(int i = 1; i <= n; i++) {
      pre[i] = i;
    }
    memset(s, 0, sizeof s);
    for(int i = 2; i <= n; i++) {
      for(int j = 2; i * j <= n; j++) {
        unite(i, i*j);
      }
    }
    for(int i = 2; i <= n; i++) {
      for(int j = 2; i * j <= n; j++) {
        s[find(i)] += (LL)j << 2LL;
      }
    }
    LL ret = 0;
    for(int i = 1; i <= n; i++) ret = max(ret, s[i]);
    printf("%I64d\n", ret);
  }
  return 0;
}