poj3635java题解

POJ3635是一道经典的数学题，需要使用一些数学知识和算法进行解决。

题目描述：

给定四个正整数 a、b、p 和 k，求 a^b^p mod k 的值。

解题思路：

首先，我们可以将指数 b^p 写成二进制形式：b^p = c0 * 2^0 + c1 * 2^1 + c2 * 2^2 + ... + ck * 2^k，其中 ci 为二进制数的第 i 位。

然后，我们可以通过快速幂算法来计算 a^(2^i) mod k 的值。具体来说，我们可以用一个变量 x 来存储 a^(2^i) mod k 的值，然后每次将 i 加 1，如果 ci 为 1，则将 x 乘上 a^(2^i) mod k，最后得到 a^b^p mod k 的值。

代码实现：

以下是 Java 的代码实现：

import java.util.*;
import java.math.*;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
BigInteger a = sc.nextBigInteger();
BigInteger b = sc.nextBigInteger();
BigInteger p = sc.nextBigInteger();
BigInteger k = sc.nextBigInteger();
BigInteger ans = BigInteger.ONE;
for (int i = 0; i < p.bitLength(); i++) {
if (b.testBit(i)) {
ans = ans.multiply(a.modPow(BigInteger.ONE.shiftLeft(i), k)).mod(k);
}
}
System.out.println(ans);
}
}

其中，bitLength() 函数用于获取二进制数的位数，testBit() 函数用于判断二进制数的第 i 位是否为 1，modPow() 函数用于计算 a^(2^i) mod k 的值，multiply() 函数用于计算两个 BigInteger 对象的乘积，mod() 函数用于计算模数。

时间复杂度：

快速幂算法的时间复杂度为 O(log b^p)，其中 b^p 为指数。由于 b^p 的位数不超过 32，因此时间复杂度为 O(log 32) = O(1)。

总结：

POJ3635 是一道经典的数学题，需要使用快速幂算法来求解。在实现时，需要注意 BigInteger 类的使用方法，以及快速幂算法的细节。