impl Solution {
fn dfs(graph: &Vec<Vec<usize>>, nodes: &mut Vec<usize>, parent: usize, node: usize) -> i64 {
nodes.push(node);
let mut path = 1;
for child in graph[node].iter() {
if child != &parent {
path += Solution::dfs(graph, nodes, node, *child);
}
}
path
}
pub fn count_paths(n: i32, edges: Vec<Vec<i32>>) -> i64 {
let mut graph: Vec<Vec<usize>> = vec![vec![]; n as usize + 1];
let mut is_prime = vec![true; n as usize + 1];
let mut ways= vec![0_i64; n as usize + 1];
let mut nodes: Vec<usize> = vec![];
let (mut ans, mut sum) = (0, 1);
// 筛法求质数
is_prime[1] = false;
for i in 2..=(n as f32).sqrt() as usize {
if is_prime[i] {
for j in (i.pow(2)..=n as usize).step_by(i) {
is_prime[j] = false;
}
}
}
for edge in edges.into_iter() {
if !is_prime[edge[1] as usize] {
graph[edge[0] as usize].push(edge[1] as usize);
}
if !is_prime[edge[0] as usize] {
graph[edge[1] as usize].push(edge[0] as usize);
}
}
for i in 1..=n as usize {
if is_prime[i] {
sum = 1;
for child in graph[i].iter() {
if ways[*child] == 0 {
nodes.clear();
let temp = Solution::dfs(&graph, &mut nodes, i, *child);
for node in nodes.iter() {
ways[*node] = temp;
}
}
ans += sum * ways[*child];
sum += ways[*child];
}
}
}
ans
}
}
# 标记 10**5 以内的质数
MX = 10 ** 5 + 1
is_prime = [True] * MX
is_prime[1] = False
for i in range(2, isqrt(MX) + 1):
if is_prime[i]:
for j in range(i * i, MX, i):
is_prime[j] = False
class Solution:
def countPaths(self, n: int, edges: List[List[int]]) -> int:
g = [[] for _ in range(n + 1)]
for x, y in edges:
g[x].append(y)
g[y].append(x)
def dfs(x: int, fa: int) -> None:
nodes.append(x)
for y in g[x]:
if y != fa and not is_prime[y]:
dfs(y, x)
ans = 0
size = [0] * (n + 1)
for x in range(1, n + 1):
if not is_prime[x]: # 跳过非质数
continue
s = 0
for y in g[x]: # 质数 x 把这棵树分成了若干个连通块
if is_prime[y]:
continue
if size[y] == 0: # 尚未计算过
nodes = []
dfs(y, -1) # 遍历 y 所在连通块，在不经过质数的前提下，统计有多少个非质数
for z in nodes:
size[z] = len(nodes)
# 这 size[y] 个非质数与之前遍历到的 s 个非质数，两两之间的路径只包含质数 x
ans += size[y] * s
s += size[y]
ans += s # 从 x 出发的路径
return ans
class Solution {
private final static int MX = (int) 1e5;
private final static boolean[] np = new boolean[MX + 1]; // 质数=false 非质数=true
static {
np[1] = true;
for (int i = 2; i * i <= MX; i++) {
if (!np[i]) {
for (int j = i * i; j <= MX; j += i) {
np[j] = true;
}
}
}
}
public long countPaths(int n, int[][] edges) {
List<Integer>[] g = new ArrayList[n + 1];
Arrays.setAll(g, e -> new ArrayList<>());
for (var e : edges) {
int x = e[0], y = e[1];
g[x].add(y);
g[y].add(x);
}
long ans = 0;
int[] size = new int[n + 1];
var nodes = new ArrayList<Integer>();
for (int x = 1; x <= n; x++) {
if (np[x]) { // 跳过非质数
continue;
}
int sum = 0;
for (int y : g[x]) { // 质数 x 把这棵树分成了若干个连通块
if (!np[y]) {
continue;
}
if (size[y] == 0) { // 尚未计算过
nodes.clear();
dfs(y, -1, g, nodes); // 遍历 y 所在连通块，在不经过质数的前提下，统计有多少个非质数
for (int z : nodes) {
size[z] = nodes.size();
}
}
// 这 size[y] 个非质数与之前遍历到的 sum 个非质数，两两之间的路径只包含质数 x
ans += (long) size[y] * sum;
sum += size[y];
}
ans += sum; // 从 x 出发的路径
}
return ans;
}
private void dfs(int x, int fa, List<Integer>[] g, List<Integer> nodes) {
nodes.add(x);
for (int y : g[x]) {
if (y != fa && np[y]) {
dfs(y, x, g, nodes);
}
}
}
}
const mx int = 1e5 + 1
var np = [mx]bool{1: true}
func init() { // 质数=false 非质数=true
for i := 2; i*i < mx; i++ {
if !np[i] {
for j := i * i; j < mx; j += i {
np[j] = true
}
}
}
}
func countPaths(n int, edges [][]int) (ans int64) {
g := make([][]int, n+1)
for _, e := range edges {
x, y := e[0], e[1]
g[x] = append(g[x], y)
g[y] = append(g[y], x)
}
size := make([]int, n+1)
var nodes []int
var dfs func(int, int)
dfs = func(x, fa int) {
nodes = append(nodes, x)
for _, y := range g[x] {
if y != fa && np[y] {
dfs(y, x)
}
}
}
for x := 1; x <= n; x++ {
if np[x] { // 跳过非质数
continue
}
sum := 0
for _, y := range g[x] { // 质数 x 把这棵树分成了若干个连通块
if !np[y] {
continue
}
if size[y] == 0 { // 尚未计算过
nodes = []int{}
dfs(y, -1) // 遍历 y 所在连通块，在不经过质数的前提下，统计有多少个非质数
for _, z := range nodes {
size[z] = len(nodes)
}
}
// 这 size[y] 个非质数与之前遍历到的 sum 个非质数，两两之间的路径只包含质数 x
ans += int64(size[y]) * int64(sum)
sum += size[y]
}
ans += int64(sum) // 从 x 出发的路径
}
return
}
