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