MENU

Catalog

    快速幂

    January 13, 2019 • Read: 545 • 算法

    首先看一道例题UVa 10006

    题目大意是说对于任意的$1 < x < n$都有$x^n\equiv x(mod n)$成立的合数$n$称为Carmichael Number,对于给定的整数$n$,判断它是不是Carmichael Number

    此题中,有n个待检查的数,如果每个数都按照定义$O(n)$的复杂度来计算幂,则总的复杂度为$O(n^2)$,不能满足要求。考虑一下加速幂运算的方法,如果$n = 2^k$,可以将其表示为

    $$ x^n = x^{2^k} = ((x^2)^2)... $$

    只要做k次平方运算就可以求得。由此我们可以想到,先将n表示为2的幂次的和

    $$ n = 2^{k&#095;1} + 2^{k&#095;2} + 2^{k&#095;3}+... $$

    则有

    $$ x^n = x^{2^{k&#095;1}}x^{2^{k&#095;2}}x^{2^{k&#095;3}}... $$

    只要在依次求$x^{2^i}$得同时进行计算就行了,最终得到$O(logn)$计算幂运算的算法

    例如$x^{22} = x^{16} \times x^{4} \times x^{2}$(22转成二进制是10110)

    long mod_pow(long x, long n, long mod) {
        long res = 1;
        while (n > 0) {
            if ((n & 1) == 1)
                res = res * x % mod;
            x = x * x % mod;
            n >>= 1;
        }
        return res;
    }

    AC代码

    import java.util.Scanner;
    
    public class Main {
        static boolean[] is_prime = new boolean[65005];
        static int[] prime = new int[65005];
    
        public static void main(String[] args) {
            sieve(65000);
            Scanner cin = new Scanner(System.in);
            while (cin.hasNext()) {
                boolean flag = true;
                int n = cin.nextInt();
                if (n == 0)
                    return;
                if (is_prime[n])
                    System.out.println(n + " is normal.");
                else {
                    for (int i = 1; i < n; i++) {
                        if (mod_pow(i, n, n) != i) {
                            flag = false;
                            System.out.println(n + " is normal.");
                            break;
                        }
                    }
                    if (flag)
                        System.out.println("The number " + n + " is a Carmichael number.");
                }
            }
        }
    
        static void sieve(int n) {
            int p = 0;
            for (int i = 2; i <= n; i++)
                is_prime[i] = true;
            for (int i = 2; i <= n; i++)
                if (is_prime[i]) {
                    prime[p++] = i;
                    for (int j = 2 * i; j <= n; j += i)
                        is_prime[j] = false;
                }
        }
    
        static long mod_pow(long x, long n, long mod) {
            long res = 1;
            while (n > 0) {
                if ((n & 1) == 1) // 如果二进制最低位为1
                    res = res * x % mod; // 乘上x^(2^i)
                x = x * x % mod; // 将x平方
                n >>= 1;
            }
            return res;
        }
    }
    Archives Tip
    QR Code for this page
    Tipping QR Code
    Leave a Comment