题意:
给出3个正整数A B C,求A^B Mod C。
例如,3 5 8,3^5 Mod 8 = 3。
分析:
快速幂模板题。
快速幂:
1.自然数的拆分
对于任何的自然数, 可以把它用形如1001的二进制码表示,进而写成形如 20 + 23 的形式。
这一步的实现:
- 对任意自然数a, 当且仅当 a&1 == 1为真时,其二进制码最低位为1.
- 通过位运算, 将可将其二进制码的任意一端的任意位舍去。
2.因子的迭代
我们需要遍历底数的 20,21,22,23......次方。
这一步的实现:
- 2n+ 2n=2n+1
- ca+b=ca * cb
实现:
import java.util.*; public class Main { public static long C; public static long qPow(long a, long b) { long ans = 1; long base = a; while (b>0) { if ((b & 1) > 0) { ans = ((ans%C)*(base%C))%C; } base = ((base%C)*(base%C))%C; b >>= 1; } return ans; } public static void main(String[] args) { Scanner input = new Scanner(System.in); long a = input.nextLong(); long b = input.nextLong(); C = input.nextInt(); System.out.printf("%d ",qPow(a,b)); input.close(); } }
注意:
一般使用长整形。