java求原根_HDU4992 求所有原根

好的，关于 HDU4992 求所有原根的问题，我可以给出以下解答：

1. 首先，我们需要知道什么是原根。原根是指模 n 意义下，所有与 n 互质的数 a 的最小正整数 k 次幂对 n 取模的值覆盖了所有与 n 互质的数。简单来说，就是如果一个数 a 是模 n 意义下的原根，那么 a 的任何正整数次幂对 n 取模的值都不相同，且能覆盖所有与 n 互质的数。

2. 为了求模 n 意义下的所有原根，我们需要先求出与 n 互质的数的个数 phi(n)。phi(n) 可以使用欧拉函数求出。

3. 然后，我们需要枚举模 n 意义下的所有数，判断它是否是原根。具体来说，对于每个 a，我们需要判断 a 的每个小于 phi(n) 的正整数次幂对 n 取模的值是否都不相同，且能覆盖所有与 n 互质的数。如果是，那么 a 就是模 n 意义下的原根。

4. 代码实现可以参考以下 Java 代码：

import java.util.*;

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

    static int phi(int n) {
        int res = n;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                res = res / i * (i - 1);
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        if (n > 1) {
            res = res / n * (n - 1);
        }
        return res;
    }

    static int pow(int a, int b, int mod) {
        int res = 1;
        while (b > 0) {
            if ((b & 1) != 0) {
                res = res * a % mod;
            }
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }

    static boolean check(int a, int n, int phi) {
        for (int i = 1, j = pow(a, i, n); i <= phi; i++, j = j * a % n) {
            if (j == 1) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int phi = phi(n);
            List<Integer> ans = new ArrayList<>();
            for (int i = 1; i < n; i++) {
                if (gcd(i, n) == 1 && check(i, n, phi)) {
                    ans.add(i);
                }
            }
            Collections.sort(ans);
            for (int x : ans) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
    }
}

其中，gcd 函数用于求最大公约数，phi 函数用于求欧拉函数，pow 函数用于快速幂求模，check 函数用于判断一个数是否是原根。在主函数中，我们依次读入每个 n，求出 phi(n)，然后枚举模 n 意义下的所有数，判断它是否是原根，将所有原根存入一个 List 中，最后排序输出即可。

希望我的回答能够帮到你，如果你有任何问题，欢迎随时提出。