目录
快速幂
费马小定理
一、试题 算法训练 A的B的C次方次方
快速幂
- 快速幂是一种用于快速计算幂运算的算法。
- 计算复杂度 O(log n)
- 基本思想是利用指数 n 的二进制展开形式，将
转化为多个 a 的幂的乘积，然后通过迭代快速计算。
快速幂的示例代码：
public class FastExponentiation {
// 使用快速幂来计算 x 的 n 次方
public static long fastExponentiation(int x, int n) {
if (n == 0) {
return 1; // 如果 n 等于 0，任何数的 0 次方都是 1
}
if (n % 2 == 0) {
long temp = fastExponentiation(x, n / 2); // 如果 n 是偶数，将问题分解为计算 x^(n/2)
return temp * temp; // 结果即为 x^(n/2) 的平方
} else {
long temp = fastExponentiation(x, (n - 1) / 2); // 如果 n 是奇数，则先计算 x^((n-1)/2)
return temp * temp * x; // 结果即为 x^((n-1)/2) 的平方再乘以 x
}
}
public static void main(String[] args) {
int base = 2; // 底数
int exponent = 10; // 指数
long result = fastExponentiation(base, exponent); // 计算 2 的 10 次方
System.out.println(base + " 的 " + exponent + " 次方结果为：" + result);
}
}
费马小定理
费马小定理是数论中的一个重要定理，它提供了一种在模数下求指数幂的快速计算方法。
费马小定理的表述如下：
模数 p 是一个质数，并且底数 a 不是 p 的倍数，则有： a^(p-1) ≡ 1 (mod p)
其中，a^(p-1) 表示 a 的 p-1 次方。
简而言之，费马小定理公式：a ^ b mod p = a ^ (b mod (p-1)) mod p
一、试题 算法训练 A的B的C次方次方
分析：
- 套用快速幂的代码
- 注意两点：
- 1、取余时，在每一步计算中都需要对结果取模以防止整数溢出
- 2、使用费马小定理来简化指数幂的计算，减少计算量
- 费马小定理的应用前提是模数 p 是一个质数，并且底数 a 不是 p 的倍数
模数 p 是一个质数，并且底数 a 不是 p 的倍数，则有费马小定理公式：a ^ b mod p = a ^ (b mod (p-1)) mod p
如果不用费马小定理，只能拿80分
import java.util.Scanner;
public class Main {
private static final int mod = 1000000007;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long a = scanner.nextLong();
long b = scanner.nextLong();
long c = scanner.nextLong();
long tmp = fastExponentiation(a, fastExponentiation(b, c, mod-1), mod);
System.out.println(tmp);
}
public static long fastExponentiation(long x,long n,int mod) {//快速幂
if(n==0) {
return 1;
}
if(n%2==0) {//偶数次方
long temp=fastExponentiation(x,n/2,mod);
return temp*temp%mod;
}else {//奇数次方
long temp=fastExponentiation(x,(n-1)/2,mod);
temp=temp*temp%mod;//在每一步计算中都需要对结果取模以防止整数溢出
return temp*x%mod;
}
}
}
