51nod 1046 快速幂

51nod1046：快速幂

总结：

快速幂就是快速算底数的n次幂。时间复杂度为 O(log₂N)，是朴素幂运算O(N)算法的改进。
(b & 1) == 1等价于b%2==1，用来判断奇偶。
b >>= 1等价于b=b/2，用来转换奇偶。
其实网上很多代码都采用二进制的写法是因为效率更高更花哨而已，其实完全可以不用，看个人习惯吧，主要考的还是时间复杂的优化

import java.util.Scanner;

public class Main {

	public static long pow2(long a, long b, long c) {// (A^B)%C
		long ans = 1;// 任何数的零次方都等于1
		while (b != 0) {
			if ((b & 1) == 1)// 如果是奇数
				ans = (ans * a) % c;
			b >>= 1;// 奇偶交替
			a = (a * a) % c;// 记录
		}
		return ans % c;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		long A, B, C;
		while (in.hasNext()) {
			A = in.nextLong();
			B = in.nextLong();
			C = in.nextLong();
			System.out.println(pow2(A, B, C));
		}
	}
}