解題區/解題區 - UVa

UVa 12858 - Even distribution

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

帶小孩子出門旅遊，每到一個地方會得到指定個數的糖果，抵達時必須將糖果均分給每一個小孩才行，現在旅遊並沒有規劃路線，在所有的路線情況下，能攜帶的小孩子個數有多少種情況。

也就是在某些情況，例如攜帶質數個小孩出門，有可能怎麼走都沒辦法均分，而導致小孩之間爭奪糖果的情況。在同一種路線下，會盡可能攜帶最大量的小孩出門。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
2 1
1 9
1 2
4 2
1 2 3 4
1 3
1 2
4 3
30 42 105 70
2 4
1 2
2 3

Sample Output

1
2
3
2
4
11

Solution

Even distribution 均勻分布

對於每一個地方紀錄可以攜帶的小孩數量，用一個 set<int> 維護。

接著不斷地更新走到別的地點，路徑之間取 gcd 最大公因數，然後將所有地點的情況聯集起來即可。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h> 
#include <set>
#include <queue> 
#include <vector>
#include <algorithm>
using namespace std;
int C[65536];
vector<int> g[65536];
int search(int n) {
    set<int> S[65536], UNION;
    queue<int> Q, P;
    int u, v, p, gg;
    for (int i = 0; i < n; i++)
        Q.push(i), P.push(C[i]), S[i].insert(C[i]), UNION.insert(C[i]);
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        p = P.front(), P.pop();
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            gg = __gcd(p, C[v]);
            if (S[v].find(gg) == S[v].end()) {
                S[v].insert(gg), UNION.insert(gg);
                Q.push(v), P.push(gg);
            }
        }
    }
    int ret = UNION.size();
    return ret;
}
int main() {
    int n, m, x, y;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &C[i]);
            g[i].clear();
        }
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        printf("%d\n", search(n));
    }
    return 0;
}
/*
2 1
1 9
1 2
4 2
1 2 3 4
1 3
1 2
4 3
30 42 105 70
2 4
1 2
2 3
*/