头像

popo_3


访客:343

离线:3小时前



popo_3
2天前
import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = in.readLine().split(" ");
        int n = Integer.parseInt(strs[0]);
        int m = Integer.parseInt(strs[1]);
        int[] parent = new int[n+1];
        int[] size = new int[n+1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        while (m-- > 0) {
            strs = in.readLine().split(" ");
            if (strs[0].equals("C")) {
                int a = Integer.parseInt(strs[1]);
                int b = Integer.parseInt(strs[2]);
                if (find(parent, a) == find(parent, b)) continue;
                size[find(parent, b)] += size[find(parent, a)];
                parent[find(parent, a)] = find(parent, b);
            } else if (strs[0].equals("Q1")) {
                int a = Integer.parseInt(strs[1]);
                int b = Integer.parseInt(strs[2]);
                System.out.println(find(parent, a) == find(parent, b) ? "Yes" : "No");
            } else if (strs[0].equals("Q2")){
                int a = Integer.parseInt(strs[1]);
                System.out.println(size[find(parent, a)]);
            }
        }
    }

    private static int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }
}


活动打卡代码 AcWing 836. 合并集合

popo_3
2天前
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] str = in.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        int[] parent = new int[n+1];
        for (int i = 1; i <= n; i++) parent[i] = i;
        while (m-- > 0) {
            str = in.readLine().split(" ");
            int a = Integer.parseInt(str[1]);
            int b = Integer.parseInt(str[2]);
            if (str[0].equals("M")) {
                parent[find(parent, a)] = find(parent, b);
            } else {
                System.out.println(find(parent, a) == find(parent, b) ? "Yes" : "No");
            }
        }
    }

    private static int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }
}


活动打卡代码 AcWing 838. 堆排序

popo_3
7天前
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int[] heap = new int[n];
        for (int i = 0; i < n; i++) {
            heap[i] = in.nextInt();
        }
        for (int i = n / 2 - 1; i >= 0; i--) {
            adjust(heap, i, n);
        }

        for (int i = n - 1; i >= 0; i--) {
            swap(heap, 0, i);
            adjust(heap, 0, i);
        }

        for (int i = 0; i < m; i++) {
            System.out.print(heap[i] + " ");
        }
    }

    private static void swap(int[] heap, int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    private static void adjust(int[] heap, int parent, int n) {
        int temp = heap[parent];
        int lchild = 2 * parent + 1;
        while (lchild < n) {
            int rchild = lchild + 1;
            if (rchild < n && heap[rchild] > heap[lchild]) lchild++;
            if (temp > heap[lchild]) break;
            heap[parent] = heap[lchild];
            parent = lchild;
            lchild = parent * 2 + 1;
        }
        heap[parent] = temp;
    }
}


活动打卡代码 AcWing 876. 快速幂求逆元

popo_3
7天前
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n-- > 0) {
            int a = in.nextInt(), p = in.nextInt();
            if (a % p == 0) System.out.println("impossible");
            else {
                long res = quickMi(a, p-2, p);
                System.out.println(res);
            }
        }
    }


    private static long quickMi(int a, int b, int p) {
        long res = 1, base = a;
        while (b != 0) {
            if ((b & 1) == 1) {
                res = res * base % p;
            }
            b = b >> 1;
            base = base * base % p;
        }
        return res;
    }
}


活动打卡代码 AcWing 875. 快速幂

popo_3
9天前
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n-- > 0) {
            int a = in.nextInt(), b = in.nextInt(), p = in.nextInt();
            long res = quickMi(a, b, p);
            System.out.println(res);
        }
    }

    private static long quickMi(int a, int b, int p) {
        long res = 1, base = a;
        while (b != 0) {
            if ((b & 1) == 1) res = res * base % p;
            b = b >> 1;
            base = base * base % p;
        }
        return res;
    } 
}


活动打卡代码 AcWing 873. 欧拉函数

popo_3
9天前
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n-- > 0) {
            int x = in.nextInt();
            int res = x;
            for (int i = 2; i <= x / i; i++) {
                if (x % i == 0) {
                    res = res / i * (i-1);
                    while (x % i == 0) {
                        x /= i;
                    }
                }
            }
            if (x > 1) res = res / x * (x - 1);
            System.out.println(res);
        }
    }
}


活动打卡代码 AcWing 872. 最大公约数

popo_3
9天前
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n-- > 0) {
            int a = in.nextInt(), b = in.nextInt();
            int gongYueShu = gcd(a, b);
            System.out.println(gongYueShu);
        }
    }

    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}


活动打卡代码 AcWing 871. 约数之和

popo_3
9天前
import java.util.*;
public class Main {
    public static final long mod = (long)Math.pow(10, 9) + 7;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Map<Integer, Integer> map = new HashMap<>();
        int n = in.nextInt();
        while (n-- > 0) {
            int x = in.nextInt();
            for (int i = 2; i <= x / i; i++) {
                while (x % i == 0) {
                    x /= i;
                    map.put(i, map.getOrDefault(i, 0) + 1);
                }
            }
            if (x > 1) map.put(x, map.getOrDefault(x, 0) + 1);
        }
        long res = 1;
        for (Integer key : map.keySet()) {
            int p = key, a = map.get(key);
            long t = 1;
            while (a-- > 0) {
                t = (p * t + 1) % mod;
            }
            res = (res * t) % mod;
        }
        System.out.println(res % mod);
    }
}


活动打卡代码 AcWing 870. 约数个数

popo_3
10天前
import java.util.*;
public class Main {
    public static final long mod = (long)(Math.pow(10, 9) + 7);
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Map<Integer, Integer> map = new HashMap<>();
        int n = in.nextInt();
        while (n-- > 0) {
            int a = in.nextInt();
            for (int i = 2; i <= a / i; i++) {
                while (a % i == 0) {
                    a /= i;
                    map.put(i, map.getOrDefault(i, 0) + 1);
                }
            }
            if (a > 1) map.put(a, map.getOrDefault(a, 0) + 1);
        }
        long res = 1;
        for (Integer key : map.keySet()) {
            res = (res * (map.get(key) + 1)) % mod;
        }
        System.out.println(res % mod);
    }
}


活动打卡代码 AcWing 869. 试除法求约数

popo_3
10天前
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n-- > 0) {
            int a = in.nextInt();
            List<Integer> divisors = getDivisors(a);
            for (Integer divisor : divisors) {
                System.out.print(divisor + " ");
            }
            System.out.println();
        }
    }

    private static List<Integer> getDivisors(int a) {
        List<Integer> divisors = new ArrayList<>();
        for (int i = 1; i <= a / i; i++) {
            if (a % i == 0) {
                divisors.add(i);
                if (i != a / i) {
                    divisors.add(a / i);
                }
            }
        }
        Collections.sort(divisors);
        return divisors;
    }
}