快速幂

首先看一道例题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;
    }
}