package erfencimi;

import java.util.Scanner;

public class Power {

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);

		//输入a和n数值

		System.out.print("请输入 a 的值:");

		int a = scanner.nextInt();

		System.out.print("请输入 n 的值:");

		int n = scanner.nextInt();

		int c=0;

		System.out.println("a = " + a + "\t" + "n = " + n);

		//打印输出二分过程

		for(int b=1;b<=n;n=n/2)

		{

			System.out.println(a + "的" + n + "次方为(第"+c+"次二分）：" + function(a, n));

			c++;

		}

		c=c-1;

		//二分次数总计

		System.out.println("总共进行了" + c + "次二分！");

	}

	//求二分次幂函数

	private static long function(int a, int n) {

		if(n == 1) { 			//指数是1时直接返回数字a

			return a;

		} else {

			if(n % 2 == 0) {	//如果是偶数次幂直接将指数进行二分

				return (int)Math.pow(function(a, n/2), 2);

			} else {			//如果是奇数次幂将指数减一再进行二分

				return (int)Math.pow(function(a, (n-1)/2), 2) * a;

			}

		}

	}

}