先来一个什么是快速幂运算的讲解博客网址点击打开链接
数值的整数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
题目链接：https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00?tpId=13&tqId=11165&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
AC代码：
代码语言：javascript复制public class Solution {
public double Power(double base, int exponent) {
if (base == 0) return 0.0;
if (exponent == 0) return 1.0;
double t = 1.0;
double b = base;
boolean f = true;
if (exponent < 0) {
exponent = -exponent;
f = false;
}
while (exponent != 0) {
if ((exponent & 1) == 1) {
t *= b;
}
exponent >>= 1;
b *= b;
}
return f ? t : 1 / t;
}
}注意，可能会有负数，比如2的-3次方
这里要写的就是它的一个应用，包含了埃氏筛法算区间素数的方法
关于埃氏筛法可以看我的另一篇博客http://blog.csdn.net/qq_34115899/article/details/79498829
题目：Carmichael Numbers (UVa No.10006)
大致意思是：我们把对任意的1<x<n都有xn≡x(mod n)成立的合数n称为Carmichael Numbers。对于给定的整数n，请判断它是不是Carmichael Numbers。（批注：a和b除以m后所得的余数相等记作a≡b(mod m)）
限制条件 2<n<65000
样例:
输入： 输入： 输入： 输入： 输入： 输入：
17 561 4 1729 1109 431
输出： 输出： 输出： 输出： 输出： 输出：
NO YES NO YES NO NO
代码语言：javascript复制import java.util.Scanner;
/*不利用语言特性任何语言都可以写*/
public class Main {
public static boolean[] is_prime = new boolean[65001];
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
long n = cin.nextLong();
cin.close();
boolean flag = true;
sieve(n); // 记录n以内，哪些是素数
if (is_prime[(int) n]) { // 是素数就不合题意
flag = false;
} else {
for (int i = 2; i < n; i) { // 1<x<n都有xn≡x(mod n)成立,即从1~n的x都有xn mod n恒等于x mod n,满足就是YES否则NO
if (mod_pow(i, n, n) != i % n) {
flag = false;
break;
}
}
}
if (flag) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
/*埃氏筛法原理：先将2到n范围内的所有整数写下来。其中最小的数字2是素数。将表中所有2的倍数都划去。
表中剩余的最小数字是3，它不能被更小的数整除，所以是素数。再将表中所有3的倍数都划去。
依次类推，如果表中剩余的最小数字是m时，m就是素数。然后将表中的所有m的倍数都划去。像这样反复操作，就能依次枚举n以内的素数*/
public static void sieve(long n) { // 埃氏筛法复杂度O（nlognlogn）看作线性也可以
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i) {
is_prime[i] = true;
}
for (int i = 2; i <= n; i) {
if (is_prime[i]) {
for (int j = i << 1; j <= n; j = i) {
is_prime[j] = false;
}
}
}
}
public static long mod_pow(long x, long n, long mod) { // java的long是64位，c 的long long是64位，long是32位
long res = 1;
while (n > 0) {
if ((n & 1) == 1) {
res = res * x % mod;
}
x = x * x % mod;
n >>= 1;
}
return res;
}
}接下来如果使用java语言特性用BigInteger的话很方便，但可能超时
代码语言：javascript复制import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static boolean[] is_prime = new boolean[65001];
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
cin.close();
boolean flag = true;
sieve(n);
if (is_prime[n]) {
flag = false;
} else {
for (int i = 2; i < n; i) {
BigInteger ii = new BigInteger(i "");
if (ii.pow(n).mod(new BigInteger(n "")).intValue() != i % n) {
flag = false;
break;
}
}
}
if (flag) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
public static void sieve(long n) {
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i) {
is_prime[i] = true;
}
for (int i = 2; i <= n; i) {
if (is_prime[i]) {
for (int j = i << 1; j <= n; j = i) {
is_prime[j] = false;
}
}
}
}
}
