【刷题笔记】第七天

文章目录

- [924. 尽量减少恶意软件的传播](https://leetcode.cn/problems/minimize-malware-spread/)
- - 方法一，并查集
  - 方法二，dfs
[GCD and LCM ](https://vjudge.net.cn/problem/HDU-4497#author=KING_LRL)

924. 尽量减少恶意软件的传播

如果移除一个感染节点可以避免连通图内节点的感染，那么该节点可能是最终的答案

我们要找避免连通图内节点感染的最大值，也就是求最大的含感染节点的连通图（连通图内只能有一个感染节点）

方法一，并查集

首先我们构建连通图，并统计连通图内的节点个数

然后求最大的含感染节点的连通图

看到连通图，就想到并查集

class Solution {
    int n;
    int[] p;
    int[] size; // 记录集合内的元素个数
    public int find(int i) {
        if (i != p[i]) {
            p[i] = find(p[i]);
        }
        return p[i];
    }
    public void union(int a, int b) {
        int aFather = find(a);
        int bFather = find(b);
        if (aFather != bFather) {
            p[bFather] = aFather;
            size[aFather] += size[bFather];
        }
    }
    public int minMalwareSpread(int[][] graph, int[] initial) {
        n = graph.length;
        p = new int[n];
        size = new int[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
            size[i] = 1;
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (graph[i][j] == 1) {
                    union(i, j);
                }
            }
        }

        Arrays.sort(initial);
        // 维护感染节点所在的集合
        Map<Integer, ArrayList<Integer>> map = new HashMap<>(); // key:感染节点的代表节点，value：代表节点所在集合的感染情况(哪些节点已经感染了)
        for (int x : initial) {
            int xFather = find(x);
            if (!map.containsKey(xFather)) {
                map.put(xFather, new ArrayList<>());
            }
            ArrayList<Integer> list = map.get(xFather);
            list.add(x);
        }

        int cnt = 0; // 避免感染节点的最大值
        int ans = n; // 要移除的索引
        for (Integer key : map.keySet()) {
            ArrayList<Integer> value = map.get(key);
            if (value.size() > 1) {
                // 如果集合内的感染节点数超过1，那么移除任意哪个节点，都不能避免该集合内节点感染
                continue;
            }
            // value.size()肯定为1

            int t = value.get(0); // value中索引最小的感染节点
            int tFather = find(t);
            if (size[tFather] > cnt) {
                cnt = size[tFather];
                ans = t;
            } else if (size[tFather] == cnt && t < ans) {
                // 索引更小
                ans = t;
            }
        }
        // ans = n，表示没有找到最大的含感染节点的连通图，也就是说移除任何一个感染节点，最终的感染节点数是一样的
        return ans == n ? initial[0] : ans;
    }
}

方法二，dfs

求最大的连通块，dfs当然也能做

需要注意的是我们要求的连通块是只含有一个感染节点的连通块。

那么如何标记我们搜索的连通块是想要的连通块呢？
可以通过设置节点状态来判断，
一个感染节点也没找到，状态为-1
找到了第一个感染节点，状态为x （感染节点的编号）
又找到了感染节点，状态为-2

所以在搜索完一个连通块后，判断状态是否大于等于0，只有大于等于0的连通块才是我们想要的连通块。

class Solution {
    int n;
    boolean[] vis;
    boolean[] isInitial; // 判断是否是感染节点

    int nodeState = -1; // -1标识初始状态，x(大于等于0)找到一个感染节点，-2找到两个感染节点
    int size; // 计算连通块内的节点个数

    public void dfs(int x, int[][] graph) {
        vis[x] = true;
        size++;
        if (isInitial[x]) {
            // x是感染节点
            if (nodeState == -1) {
                // 找到了第一个感染节点
                nodeState = x;
            } else {
                nodeState = -2;
            }
        }
        for (int y = 0; y < graph[x].length; ++y) {
            if (vis[y]) continue;
            if (graph[x][y] == 1) {
                dfs(y, graph);
            }
        }
    }
    public int minMalwareSpread(int[][] graph, int[] initial) {
        n = graph.length;
        vis = new boolean[n];
        isInitial = new boolean[n];
        for (int i : initial) {
            isInitial[i] = true;
        }
        int maxSize = 0;
        int ans = n;
        Arrays.sort(initial);
        for (int i : initial) {
            if (vis[i]) continue;
            nodeState = -1;
            size = 0;
            dfs(i, graph);
            if (nodeState >= 0) {
                if (size > maxSize) {
                    maxSize = size;
                    ans = i;
                } else if (size == maxSize && i < ans) {
                    ans = i;
                }
            }
        }
        return ans == n ? initial[0] : ans;
    }
}

GCD and LCM

最大公因数、最小公倍数的性质：

假设gcd(x, y) = G，lcm(x, y) = L
1. L % G == 0
2. L / G = (x / G) * (y / G)
3. gcd(kx, ky) = k gcd(x, y) = kG，所以gcd(x/G, y/G) = 1
lcm(x/G, y/G) = L/G
4. 两个互素的数的最小公倍数等于两者乘积
5. gcd(x, y) * lcm(x, y) = x y

对于此题x, y, z，假设gcd(x, y, z) = G, lcm(x, y, z) = L
我们令x’ = x/ G, y’= y/G, z’ = z /G，所以gcd(x’, y’, z’) = 1, lcm(x’, y’, z’) = L / G
所以我们将原问题转化为，(x,y,z)的最大公约数为1，最小公倍数为L/G的个数

令L’ = L / G
我们对L‘ 进行素因子分解，可得 $L'=x_1^{p_1}x_2^{p_2}... x_m^{p_m}，其中x_1,x_2, ..., x_m都是素数$ ，这里默认使用了一个结论(任何数都可以分解为若干个素数的乘积)，然后对x’，y‘，z’分解可得：
$x'=x_1^{a_1}x_2^{a_2}... x_m^{a_m}$
$y'=x_1^{b_1}x_2^{b_2}... x_m^{b_m}$
$z'=x_1^{c_1}x_2^{c_2}... x_m^{c_m}$

先看分解式的第一项 $x_1^{?_1}$
由于gcd(x’, y’, z’) = 1，所以 $a_1, b_1,c_1$ 中至少有一个是0，（假设 $a_1, b_1,c_1$ 都不为0，那么最大公约数肯定不为1，因为他们都有 $x_1$ 这个因子）
$a_1, b_1,c_1$ 中至少有一个是 $p_1$ (因为他们的最小公倍数是L‘，如果 $a_1, b_1,c_1$ 都不是 $p_1$ ，那么他们的乘积也就是公倍数（不是最小公倍数，因为xyz不一定互质）的分解不存在 $x_1^{p_1}$ 这一项)
所以 $a_1, b_1,c_1$ 至少一个是0，至少一个是 $p_1$ ，情况如下：

1个0， 2个p1， (0, p1, p1) , (p1, 0, p1), (p1, p1, 0) ，3种
2个0 , 1个p1，(0, 0, p1), (p1, 0, 0), (0, p1, 0), 3种
1个0, 1个p1，1~p1-1，(0, p1, 1~p1-1), … $A^2_3(p_1 - 1) = 6(p_1-1)$

所以总共有 $6p_1种情况$ ，这是第一项的情况数，还有第二项，第三项…
根据乘法定理，总情况数= $6p_1*6p_2...*6p_m$

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;
int main() {

	int t;
	scanf("%d", &t);
	while (t--) {
		int g, l;
		scanf("%d%d", &g, &l);
		if (l % g != 0) {
			printf("0\n");
			continue;
		}
		l = l / g;
		int x = 2; // 对l进行分解， l = 2^p1 + 3^p2 + ..
		int ans = 1;
		while (l > 1) {
			int cnt = 0; // 计算p1, p2..
			while (l % x == 0) {
				l = l / x;
				cnt++;
			}
			if (cnt > 0) {
				ans *= 6 * cnt;
			}
			
			x++;
		}
		printf("%d\n", ans);
	}

	return 0;
}