MENU

Catalog

    快速幂

    January 13, 2019 • Read: 7806 • 算法阅读设置

    首先看一道例题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_1} + 2^{k_2} + 2^{k_3}+... $$

    则有

    $$ x^n = x^{2^{k_1}}x^{2^{k_2}}x^{2^{k_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;
        }
    }
    Last Modified: June 4, 2019
    Archives Tip
    QR Code for this page
    Tipping QR Code
    Leave a Comment

    7 Comments
    1. wallace wallace

      博主这么牛逼,是怎么学的?

    2. wallace wallace

      与博主相比,我的大学白上了,还是我上了一个假大学?

    3. 渠宇 渠宇

      我也这样觉得,我想知道博主的学习路线是什么样的

      1. mathor mathor

        @渠宇算法 -> CTF皮毛,编译原理,Java -> Python -> 机器学习 -> 深度学习 -> 迎娶白富美

      2. 渠宇 渠宇

        @mathor哇!非常感谢博主,再问一个问题,博主大大现在是本科还是研究生啊。你大学学了上面的多少呀?@(哈哈)

      3. mathor mathor

        @渠宇刚考完研,今年6月本科毕业,所以这博客里全是我本科时写的

      4. 渠宇 渠宇

        @mathor好的谢谢!